$FHQ\_Treap$是平衡树的一种，它不仅支持几乎所有的平衡树的操作，而且实现特别简单，总共只有两个操作。这里来简单介绍一下。
$FHQ\_Treap$和$Treap$一样是需要用随机值来维护树的形态的，但是$FHQ\_Treap$不需要旋转来调整形态，而且用$Split$和$Merge$来实现，也就是分离与合并，也就是这两种操作，完成了平衡树的所有操作。
分离（Split）
把一棵平衡树分离成两颗，从而方便插入和删除。分离有两种做法，一种是按权值分离，一种是按子树大小分离，根据情况选择。
权值分离版：
void split(int rt,int k,int &x,int &y) { if( !rt ) x=y=0; else { if( val[rt]<=k ) x=rt, split(ch[rt][1],k,ch[rt][1],y); else y=rt, split(ch[rt][0],k,x,ch[rt][0]); pushup(rt); } }
子树大小版：
void split(int rt,int k,int &x,int &y) { if( !rt ) x=0, y=0; else { pushdown(rt); if( siz[ch[rt][0]]<k ) { x=rt, split(ch[rt][1],k-siz[ch[rt][0]]-1,ch[rt][1],y); } else { y=rt, split(ch[rt][0],k,x,ch[rt][0]); } pushup(rt); } }
合并（merge）
合并操作与左偏树的合并类似，按照优先级合并，把优先级高的作为父节点。当然，合并的时候，函数中的两个参数$x,y$要按照顺序，$x$是权值较小的，$y$是权值较大的，因为合并的时候是按照随机值来确定优先级的。（当然在函数中交换也行，不过常数大些）
int merge(int x,int y) { if( !x || !y ) return x+y; pushdown(x), pushdown(y); if( p[x]<p[y] ) { ch[x][1]=merge(ch[x][1],y); pushup(x); return x; } else { ch[y][0]=merge(x,ch[y][0]); pushup(y); return y; } }
插入新节点（insert）
先把树按照新结点的权值分离，然后再把新结点当作一棵树与两个分离出来的树合并。
inline int neo(int v) { val[++tot]=v; siz[tot]=1; p[tot]=rand(); return tot; } inline void insert(int v) { int x,y; split(root,v,x,y); root=merge(merge(x,neo(v)),y); }
删除节点（delete）
按删除节点的权值$v$把树分离成小于$v$，等于$v$，大于$v$三段，然后去掉等于$v$的树的根节点（也就是直接合并根节点的左右子树），然后合并回来。
inline void delet(int v) { int x,y,z; split(root,v,x,y); split(x,v-1,x,z); z=merge(ch[z][0],ch[z][1]); root=merge(x,merge(z,y)); }
查询权值为$k$的节点编号
按照权值分离然后输出左子树大小$+1$即可。
inline void kth(int k) { int x,y; split(root,k-1,x,y); printf("%d\n",siz[x]+1); root=merge(x,y); }
查询$k$小值
和其他平衡树一样搜索递归。
int rank(int rt,int k) { if( siz[ch[rt][0]]==k-1 ) return val[rt]; if( siz[ch[rt][0]]>=k ) return rank(ch[rt][0],k); return rank(ch[rt][1],k-siz[ch[rt][0]]-1); }
查询前驱后继
按权值分离然后查询分离出的子树的最大/最小值就行了。
inline void prev(int v) { int x,y; split(root,v-1,x,y); printf("%d\n",rank(x,siz[x])); root=merge(x,y); } inline void nex(int v) { int x,y; split(root,v,x,y); printf("%d\n",rank(y,1)); root=merge(x,y); }
//It is made by HolseLee on 27th Sep 2018 //Luogu.org P3369 #include<bits/stdc++.h> using namespace std; const int N=1e5+7; int n,root,tot; int val[N],ch[N][2],p[N],siz[N]; inline int read() { char ch=getchar(); int num=0; bool flag=false; while( ch<‘0‘ || ch>‘9‘ ) { if( ch==‘-‘ ) flag=true; ch=getchar(); } while( ch>=‘0‘ && ch<=‘9‘ ) { num=num*10+ch-‘0‘; ch=getchar(); } return flag ? -num : num; } inline void pushup(int rt) { siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1; } void split(int rt,int k,int &x,int &y) { if( !rt ) x=y=0; else { if( val[rt]<=k ) x=rt, split(ch[rt][1],k,ch[rt][1],y); else y=rt, split(ch[rt][0],k,x,ch[rt][0]); pushup(rt); } } int merge(int x,int y) { if( !x || !y ) return x+y; if( p[x]<p[y] ) { ch[x][1]=merge(ch[x][1],y); pushup(x); return x; } else { ch[y][0]=merge(x,ch[y][0]); pushup(y); return y; } } inline int neo(int v) { val[++tot]=v; siz[tot]=1; p[tot]=rand(); return tot; } inline void insert(int v) { int x,y; split(root,v,x,y); root=merge(merge(x,neo(v)),y); } inline void delet(int v) { int x,y,z; split(root,v,x,y); split(x,v-1,x,z); z=merge(ch[z][0],ch[z][1]); root=merge(x,merge(z,y)); } inline void kth(int k) { int x,y; split(root,k-1,x,y); printf("%d\n",siz[x]+1); root=merge(x,y); } int rank(int rt,int k) { if( siz[ch[rt][0]]==k-1 ) return val[rt]; if( siz[ch[rt][0]]>=k ) return rank(ch[rt][0],k); return rank(ch[rt][1],k-siz[ch[rt][0]]-1); } inline void prev(int v) { int x,y; split(root,v-1,x,y); printf("%d\n",rank(x,siz[x])); root=merge(x,y); } inline void nex(int v) { int x,y; split(root,v,x,y); printf("%d\n",rank(y,1)); root=merge(x,y); } int main() { srand(19260817); n=read(); int opt; for(int i=1; i<=n; ++i) { opt=read(); if( opt==1 ) insert(read()); else if( opt==2 ) delet(read()); else if( opt==3 ) kth(read()); else if( opt==4 ) printf("%d\n",rank(root,read())); else if( opt==5 ) prev(read()); else nex(read()); } return 0; }
原文：https://www.cnblogs.com/cytus/p/9926363.html