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)。

写法就是判断 (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 能实现哪些操作吧，请看模板题 普通平衡树。（下面全部内容为笔者自己发挥，若有更好做法请在评论区留言或私信笔者）

插入 (x)：将根以 (x) 值分裂，在中间建一个新的点合并回去即可，比较容易。
删除 (x)：将根分别以 (x-1,x) 分裂，中间一个树就是权值为 (x) 的树，把这个树替换为它左右子树合并的结果即可（因为只要删一个，相当于把根节点给删了。
查询 (x) 的排名：这个非常容易，直接按 (x-1) 分裂并输出第一个子树大小 +1 即可。
查询排名为 (x) 的数：这个可以从根节点开始，不停地判断应该往左子树走还是右子树走，判断方式就是看当前点地左子树大小 +1 和 (x) 的大小关系，若相等则直接退出。
查询 (x) 的前驱：笔者做法比较暴力，直接将数按 (x-1) 分裂，第一棵树的最后一个就是，最后一个求可以查询排名为数大小的数，用之前的函数可以求出。
查询 (x) 的后继：同前驱做法，按 (x) 分裂，第二棵树的第一个就是，同样查询排名为 1 的树即可，使用之前的函数。

具体的还是看代码吧。

代码

#include <bits/stdc++.h> #define TIME 1e3*clock()/CLOCKS_PER_SEC using namespace std; // stay organized mt19937 rnd(233); const int maxn=1e5+10; struct Node {     int ls,rs;     int siz;     int val,key; }tree[maxn]; int rt=0,tot=0; int newnode(int val) {     tot++;     tree[tot].ls=tree[tot].rs=0;     tree[tot].siz=1;     tree[tot].val=val;     tree[tot].key=rnd();     return tot; } void upd(int x) {     tree[x].siz=tree[tree[x].ls].siz+1+tree[tree[x].rs].siz; } 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); } 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;     } } int x,y,z; void ins(int val) {     split(rt,val,x,y);     rt=merge(merge(x,newnode(val)),y); } void del(int val) {     split(rt,val-1,x,y);     split(y,val,y,z);     y=merge(tree[y].ls,tree[y].rs);     rt=merge(merge(x,y),z); } int rnk(int val) {     split(rt,val-1,x,y);     int ans=tree[x].siz+1;     rt=merge(x,y);     return ans; } int kth(int now,int k) {     while(tree[tree[now].ls].siz+1!=k)     {         if(tree[tree[now].ls].siz+1>k)             now=tree[now].ls;         else         {             k-=tree[tree[now].ls].siz+1;             now=tree[now].rs;         }     }     return tree[now].val; } int pre(int val) {     split(rt,val-1,x,y);     int ans=kth(x,tree[x].siz);     rt=merge(x,y);     return ans; } int suf(int val) {     split(rt,val,x,y);     int ans=kth(y,1);     rt=merge(x,y);     return ans; } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     int t;     cin>>t;     int opt,x;     while(t--)     {         cin>>opt>>x;         if(opt==1)             ins(x);         else if(opt==2)             del(x);         else if(opt==3)             cout<<rnk(x)<<'n';         else if(opt==4)             cout<<kth(rt,x)<<'n';         else if(opt==5)             cout<<pre(x)<<'n';         else cout<<suf(x)<<'n';     }     return 0;     // you should actually read the stuff at the bottom }  /* stuff you should look for     * int overflow, array bounds     * clear the arrays?     * special cases (n=1?),     * WRITE STUFF DOWN,     * DON'T GET STUCK ON ONE APPROACH */ 

完结撒花 owo~