FHQ Treap 详解 _生活百科

鲜花一些鲜花放在前面，平衡树学了很久，但是每学一遍都忘，原因就在于我只能 70% 理解 + 30% 背板子，所以每次都忘。这次我采取了截然不同的策略，自己按照自己的理解打一遍，大获成功（？），大概打 20 min，调 10 min 结束，然后写下了这篇文章。
虽然但是，感觉 Treap 还是很强的，代码好写好调，而且可以解决很多问题（下面将会提到），好像说是常数大一点？无伤大雅吧……
Treap首先，从 Treap 的定义开始。Treap 实际上是一种笛卡尔树（笛卡尔树可以看这篇文章，每个点有两个信息 \((v_u,p_u)\)，分别表示点 \(u\) 的权值与优先度。\(v_u\) 形成一个二叉搜索树（左儿子的值 \(\leq\) 自己的值 \(\leq\) 右儿子的值），\(p_u\) 形成一个大根堆（自己的值 \(\geq\) 左右儿子的值）。
你可以利用 Treap 做很多有用的操作，但是 Treap 有一个缺点，就是如果被卡成链怎么办？
FHQ Treap这时候就需要用到 FHQ Treap，它基于 Treap 的基础上对每个点的 \(p\) 值都进行了随机化操作，这样就可以达到平衡的目的了。为什么？因为随机出来不平衡的概率很小，大多随机数都是无规律的，这样通过大根堆的性质就可以使它达到平衡，这样树高期望就是 \(O(\log n)\) 层的了，并且无法卡掉，因为随机数是程序生成的，并非数据所决定。

系统随机函数若以 srand(time(0)) 为随机种子，效果不佳，推荐使用 mt19937 rnd(233)，生成随机数更加均匀。

FHQ Treap 又叫无旋 Treap，它只需要两个核心操作 merge() 和 split() 即可完成所有的复杂操作，就像玩拼图一样把一棵树拆开再拼起来一样。下面就来具体介绍一下这两个函数到底是如何实现的。
关于 upd 函数的说明
（这个可以学完下面的再看）upd 函数，即刷新一个节点大小的函数。在 split() 中，在分裂完子树后最后应该刷新，不然可能大小信息已经被更改而不知道。同理，在 merge() 中，合并子树后也应当刷新，调不出来一定要检查一下是否因忘记刷新而错误。
split 函数split 函数实现的功能是把一棵树按照权值大小拆分成两棵树，具体来说，split(int cur,int k,int &x,int &y) 表示将以 cur 为根的子树拆分成两棵树 \(x\) 和 \(y\)，其中 \(x\) 里的权值都 \(\leq k\)，\(y\) 里的权值都 \(>k\) 。
怎么写呢？首先，为了方便返回，直接将要拆分成的两棵子树引用定义在函数参数中。先特判一下，如果要拆分的树为空，则拆分出来的两棵树也为空。不然就判断树根是否 \(\leq k\)，如果是，则树左子树都 \(\leq k\)，即属于 \(x\)，那么只要分裂右子树即可，反之亦然。

代码

void split(int cur,int k,int &x,int &y){if(!cur){x=y=0;return;}if(tree[cur].val<=k){x=cur;split(tree[x].rs,k,tree[x].rs,y);}else{y=cur;split(tree[y].ls,k,x,tree[y].ls);}upd(cur);}

merge 函数merge 函数就是把两个树 \(x,y\) 合并，保证所有 \(x\) 中的 \(v\) 都 \(\leq\) 所有 \(y\) 中的 \(v\)，具体来说，就是 int merge(int x,int y) 。
【FHQ Treap 详解】写法就是判断 \(x,y\) 中是否有空树，有的话直接返回另一个即可。不然比较两者根的有先值，如果第一个大，根据大根堆性质，显然应该合并 \(x\) 的右子树和 \(y\)，反之亦然。

代码

int merge(int x,int y){if(!x||!y)return x+y;if(tree[x].key>=tree[y].key){tree[x].rs=merge(tree[x].rs,y);upd(x);return x;}else{tree[y].ls=merge(x,tree[y].ls);upd(y);return y;}}

其他操作的实现下面来看看 FHQ Treap 能实现哪些操作吧，请看模板题普通平衡树。（下面全部内容为笔者自己发挥，若有更好做法请在评论区留言或私信笔者）