原文发表时间:2014-02-18
本文介绍用merge
(合并)和split
(分离)来实现各种操作的treap。好处?就是可以跟splay一样玩序列操作,而且还能方便的实现持久化。合起来说嘛,就是能拿一个持久化序列操作的专利。 其实直接暴力改节点的优先级然后旋到根就和splay一样了,不过还要把优先级改回来然后旋回来。另外AVL好像也可以玩持久化序列操作。
merge
就是把两棵treap合并成一棵(要求其中一棵的所有元素小于另一棵的)。
split
是把一棵treap的前若干个元素分离出来作为一棵treap,剩余的作为一棵treap。
操作的实现
插入就先把待插入的元素建成一棵treap(如果是单个元素就直接新建节点,多个的话用merge
合起来),然后从插入的位置split
开得到两棵treap,把3棵treap依次merge
即可。另外fhq在WC2012的讲稿还有讲另一种不用旋转也不用merge
/split
的写法。
删除的话用2次split
分成3棵treap
,然后把第一棵和第三棵merge
。
直接用两次split
就能提取一段。
另外说一下,这样实现的treap基本上每次操作都要用几次的merge
/split
,所以常数有点大。如果时限卡太紧的话就只能用码长换时间了吧……(大雾
接着详细地讲一下merge
和split
怎么做。是随机的优先级,、是左右儿子,是该节点的子树包含的元素个数。
merge
merge(x,y)
就是把,合并,的所有元素小于的。
如果、有一个是空的返回另一个就好了。
由于元素大小已知,要么是作为的左儿子,要么就是作为的右儿子,只需要根据随机优先级判断即可。
我的是小根堆。若,那么改为merge(rc[x],y)
,返回;否则改为merge(x,lc[y])
,返回。merge
应该挺好理解吧……
split
split(now,x,y,k)
是把里的前个元素切出来放在,剩余的放在,的所有元素小于的。我一开始的时候没想明白要怎么切,比如下面这幅图
我要切前5个元素,切出来的应该是红圈里的。但是它们不是连在一起的怎么破!然后我发现我智商下线了。谁告诉你只能切一刀了?切两刀然后接在一起不就好了么……所以可以这样写:
如果为NULL就把、都改成NULL,然后退出。
若就把改成,然后split(lc[now],x,lc[y],k)
;若就把放到,其余的放到;若就把改成,然后split(rc[now],rc[x],y,k-s[lc[now]]-1)
。
也可以加多一个判断:如果,就把改成,改成NULL,然后退出。这样会快一点。
还是用上面的例子看一看整个split
的流程吧,上面的是原来的treap,下面的两棵是分离后的结果,紫色箭头指着的是当前处理到哪一个节点,数字表示要切多少个元素。
最后得到的就是这样的:
如果要实现持久化的话,只需要把所有修改节点信息的操作改成新建节点就行了。
参考资料
范浩强 WC2012讲稿 《谈谈各种数据结构》
范浩强 网易博客 《挖掘treap的潜力》
陈立杰 国家集训队作业 《可持久化数据结构研究》
orz以上两位神犇!