用merge和split实现的treap

原文发表时间：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怎么做。 $pri$ 是随机的优先级， $lc$ 、 $rc$ 是左右儿子， $s$ 是该节点的子树包含的元素个数。

merge

merge(x,y)就是把 $x$ ， $y$ 合并， $x$ 的所有元素小于 $y$ 的。
如果 $x$ 、 $y$ 有一个是空的返回另一个就好了。
由于元素大小已知，要么是 $x$ 作为 $y$ 的左儿子，要么就是 $y$ 作为 $x$ 的右儿子，只需要根据随机优先级判断即可。
我的是小根堆。若 $pri[x]<pri[y]$ ，那么 $rc[x]$ 改为merge(rc[x],y)，返回 $x$ ；否则 $lc[y]$ 改为merge(x,lc[y])，返回 $y$ 。merge应该挺好理解吧……

split

split(now,x,y,k)是把 $now$ 里的前 $k$ 个元素切出来放在 $x$ ，剩余的放在 $y$ ， $x$ 的所有元素小于 $y$ 的。我一开始的时候没想明白要怎么切，比如下面这幅图

我要切前5个元素，切出来的应该是红圈里的。但是它们不是连在一起的怎么破！然后我发现我智商下线了。谁告诉你只能切一刀了？切两刀然后接在一起不就好了么……所以可以这样写：
如果 $now$ 为NULL就把 $x$ 、 $y$ 都改成NULL，然后退出。
若 $k\leq s[lc[now]]$ 就把 $y$ 改成 $now$ ，然后split(lc[now],x,lc[y],k)；若 $k=s[lc[now]]+1$ 就把 $rc[now]$ 放到 $y$ ，其余的放到 $x$ ；若 $k>s[lc[now]]+1$ 就把 $x$ 改成 $now$ ，然后split(rc[now],rc[x],y,k-s[lc[now]]-1)。
也可以加多一个判断：如果 $k=0$ ，就把 $y$ 改成 $now$ ， $x$ 改成NULL，然后退出。这样会快一点。
还是用上面的例子看一看整个split的流程吧，上面的是原来的treap，下面的两棵是分离后的结果，紫色箭头指着的是当前处理到哪一个节点，数字表示要切多少个元素。