“平衡树好烦啊，转来转去的，而且treap遇到区间序列问题就gg。”
“有一种不用旋转的treap，叫FHQ-treap，可以解决区间序列问题。”
正文 约定我们做出以下约定：
int ch[MAXN][3];//0 左孩子，1右孩子int val[MAXN];//每个点的权值int rnd[MAXN];//每个点的随机权值int size[MAXN];//以每个点为根的树的大小 分裂分裂有两种，一种是权值分裂，一种是排名分裂。
我们先讲权值分裂。如图，当我们遍历到一个节点时，如果它的权值小于 k， 那么它的左子树会被分到左边的树里，然后我们遍历它的右儿子，如果大于 k，则把它的右子树分到右边的树里。如果到达递归边界 now==0 怎么办呢？这里会有两种情况：
1.root=0（即第一次split），很明显要给x和y初始化，即x=y=0。
2.split到了叶子节点，此时无法继续split了，只能返回。此时的x=y=0没什么用，因为x和y会在回溯的时候通过地址符号改变。
代码：
void split(int now,int k,int &x,int &y){ if(!now) x=y=0; else if(val[now]<=k) { x=now; split(ch[now][1],k,ch[now][1],y); } else { y=now; split(ch[now][0],k,x,ch[now][0]); } update(now);//update(i)为更新size[i]大小的函数}排名分裂与权值分裂类似，即将前k个放在一颗树里，其余的放在另一棵树里。代码：
void split(int now,int k,int &x,int &y){ if(!now) x=y=0; else { if(k<=siz[ch[now][0]]) { y=now; split(ch[now][0],k,x,ch[now][0]); } else { x=now; split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y); } update(now); }} 合并如图，我们假设第一棵树的权值小于第二棵树的权值，那么我们就比较它们的随机权值。如果rnd[l]<rnd[r]，我们就保留它的左子树，另一棵树作为它的右子树；如果rnd[l]>=rnd[r]，那我们可以保留第二棵树的右子树，另一颗树作为它的左子树。代码：
int merge(int A,int B){ if(!A||!B) return A+B; if(rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); update(A); return A; } else { ch[B][0]=merge(A,ch[B][0]); update(B); return B; } }以上操作完成后，我们就可以用函数式编程的思想完成剩余的操作。
插入直接暴力merge，代码：
int new_node(int a)//新建一个节点{ size[++cnt]=1; val[cnt]=a; rnd[cnt]=rand(); return cnt;}void insert(int a)//插入 { spilt(root,a,x,y); root=merge(merge(x,new_node(a)),y);} 删除删除权值为v的点，先把整颗树以v为权值split成两棵树a,b,再把a树按照v-1分成c,d。这时候值为v的点一定为d的根，那么我们把d的两个子儿子merge起来（划重点：这一步就是去除掉v的影响），再把他们重新merge起来得到一个新的树，这颗树就去除掉了v的影响。代码：
void del(int a){ split(root,a,x,z); split(x,a-1,x,y); y=merge(ch[y][0],ch[y][1]); root=merge(merge(x,y),z);} 排名直接按照a-1的权值把树分开，那么x树中最大的应该小于等于a-1，那么a的排名就是size[x]+1。代码：
int myrank(int a){ split(root,a-1,x,y); int res=size[x]+1; root=merge(x,y); return res;} k小值不想说什么，直接看代码：
int kth(int now,int k){ while(1) { if(k<=size[ch[now][0]]) now=ch[now][0]; else if(k==size[ch[now][0]]+1) return now; else k-=size[ch[now][0]]+1,now=ch[now][1]; }} 前驱后继我们先看前驱，因为要小于a，所以我们还是按照a-1的权值划分x，现在x中最大的数一定小于等于a-1，所以我们直接输出x中最大的数就好，后继同理，不再赘述。代码：
int pre(int a){ split(root,a-1,x,y); int res=val[findKth(x,siz[x])]; root=merge(x,y); return res;}int nxt(int a){ split(root,a,x,y); int res=val[findKth(y,1)]; root=merge(x,y); return res;} 关于区间问题查询一个区间[l, r]就把一棵树split成三棵树，查中间那棵，再把它们merge回去。代码：
void add(int l,int r,int delta)//任意操作 { int x,y,z; split(root,x,y,r); split(x,z,x,l-1); addone(x,delta);//任意操作 merge(x,z,x); merge(root,x,y);} 关于可持久化fhq treap可以可持久化。如图，每次split和merge走到的所有点都新建一个即可。注意下传标记也要新建点。
本文转载至洛谷日报#43 Chanis的博文，相比原文修复了诸多代码问题
还有有疑问可以在此处寻找更多优秀文章或者在评论中提出哦~