平衡树
这里讲 非旋Treap，FHQTreap
概述
FHQTreap 的思想基于分裂和合并。
存储的信息是：
\(ls\) 和 \(rs\) 左右儿子。
\(val\) 权值
\(siz\) 子树大小。
对于 Treap 比较独特的是 \(rd\)，实际上是一个随机优先级。
对于相同权值的不同的点，不会记录成一个点，故没有记录次数的 \(cnt\)。
函数
push
更新答案，子树大小为左右儿子大小 + 1。
void push(int x){siz[x] = siz[ls[x]]+siz[rs[x]]+1;}
split
分裂，这里按照权值 \(val\) 分裂。
具体地，给定一个 \(v\)，要将原本的平衡树 \(T\) 分裂成 \(T_x\) 和 \(T_y\) 两棵。
对于任意 \(i \in T_x\) 和 \(j \in T_y\) 都有 \(val_i < v < val_j\)。
满足平衡的性质。
如果 \(val_p < v\) 那么 \(p\) 应当属于 \(T_x\) 中。那么应该向右递归。
反则向左递归。
类似二分的思想，通过左右递归，等效于二分中的 \(mid = r\) 或 \(mid = l\)。
递归边界：\(p=0\) 也就是找到最终的位置了。
void split(int p,int v,int &x,int &y){
if(!p) {
x=y=0;
return ;
}if(val[p] <= v) split(rs[p],v,rs[x=p],y);
else split(ls[p],v,x,ls[y=p]);
push(p);
}
merge
合并，是对于 split 相反的一种操作。
对于两棵平衡树 \(T_x\) 和 \(T_y\) 要将他们合并。
对于任意 \(i \in T_x\) 和 \(j \in T_y\)：
根据定义，都有 \(val_i < val_j\)。
在此，要生成随机数，也就是 \(rd\)。
如果 \(rd_x > rd_y\) 那么前者优先级更高，也就是 \(x\) 作为 \(y\) 的父节点。
再对于 \(val\) 进行比较，判断其属于左儿子还是右儿子。
例：如果 \(val_x < val_y\) 那么 \(y\) 是 \(x\) 的右儿子。
直接调用 \(merge(rs_x,y)\) 即可。
小于同理。
如果 \(x\) 和 \(y\) 有一个为空，
那么返回他们其中一个，直接 \(x \ or \ y\) 即可。
int merge(int x,int y){
if(!x||!y)return x|y;
if(rd[x]<rd[y]){
ls[y]=merge(x,ls[y]),push(y);
return y;
}
rs[x]=merge(rs[x],y),push(x);
return x;
}
new node
新建节点。
int nd(int v){
int x=++node;
val[x]=v;
rd[x]=rand();
siz[x]=1;
return x;
}
insert
插入。
插入一个 \(v\)，先将 \(val_i < v\) 的 \(i\) 分到 \(T_x\) 中。
反之分到 \(T_y\) 中。
再重新设定 root 即可。
void insert(int v){
int x=0,y=0;
split(R,v-1,x,y);
R=merge(merge(x,nd(v)),y);
}
del
删除。
删除一个 \(v\)。首先按照 \(v\) 把 \(T\) 分裂成 \(T_x\) 和 \(T_z\)。
再按照 \(v-1\) 把 \(T_x\) 分成 \(T_x\) 和 \(T_y\)。
因此此时 \(T_y\) 的权值都是 \(v\)。
但是只能删除一个。
所以直接删除 \(T_y\) 的根。
把它的左右子树合并起来。
再与 \(T_x\) 和 \(T_z\) 合并起来即可。
void del(int v){
int x=0,y=0,z=0;
split(R,v,x,z),split(x,v-1,x,y);
R=merge(merge(x,y=merge(ls[y],rs[y])),z);
}
kth
第 k 大。
当前遍历到 \(p\)。
若 \(k \le siz_ls_p\)。递归左儿子。
若 \(k=sz_ls_p + 1\)，返回 \(val_p\)。
否则，递归右儿子。
int kth(int k){
int p=R;
while(true){
if(k<=siz[ls[p]])p=ls[p];
else if(k==siz[ls[p]]+1)return val[p];
else k-=siz[ls[p]]+1,p=rs[p];
}
}
pre
前驱。
先用 \(v-1\) 分裂成 \(T_x\) 和 \(T_y\)。
所以找到 \(T_x\) 中的最大值即可。
int pre(int v){
int p=R,ans=0;
while(true){
if(!p) return ans;
else if(v<=val[p])p=ls[p];
else ans=val[p],p=rs[p];
}
}
sec
后继。
同理前驱。
int suc(int v){
int p=R,ans=0;
while(true){
if(!p) return ans;
else if(v>=val[p])p=rs[p];
else ans=val[p],p=ls[p];
}
}
rank
排名。
查询 \(v\) 排名。
按 \(v-1\) 分裂。
分裂成 \(T_x\) 和 \(T_y\)。
答案为 \(siz_x + 1\)。
最后再合并。
int rnk(int v){
int x=0,y=0,ans=0;
split(R,v-1,x,y);ans=siz[x]+1;
return R=merge(x,y),ans;
}
Code
namespace FHQTreap{
int R,node,ls[N],rs[N],val[N],rd[N],siz[N];
void push(int x){siz[x] = siz[ls[x]]+siz[rs[x]]+1;}
void split(int p,int v,int &x,int &y){
if(!p) {
x=y=0;
return ;
}if(val[p] <= v) split(rs[p],v,rs[x=p],y);
else split(ls[p],v,x,ls[y=p]);
push(p);
}int merge(int x,int y){
if(!x||!y)return x|y;
if(rd[x]<rd[y]){
ls[y]=merge(x,ls[y]),push(y);
return y;
}
rs[x]=merge(rs[x],y),push(x);
return x;
}int nd(int v){
int x=++node;
val[x]=v;
rd[x]=rand();
siz[x]=1;
return x;
}void insert(int v){
int x=0,y=0;
split(R,v-1,x,y);
R=merge(merge(x,nd(v)),y);
}void del(int v){
int x=0,y=0,z=0;
split(R,v,x,z),split(x,v-1,x,y);
R=merge(merge(x,y=merge(ls[y],rs[y])),z);
}int kth(int k){
int p=R;
while(true){
if(k<=siz[ls[p]])p=ls[p];
else if(k==siz[ls[p]]+1)return val[p];
else k-=siz[ls[p]]+1,p=rs[p];
}
}int pre(int v){
int p=R,ans=0;
while(true){
if(!p) return ans;
else if(v<=val[p])p=ls[p];
else ans=val[p],p=rs[p];
}
}int suc(int v){
int p=R,ans=0;
while(true){
if(!p) return ans;
else if(v>=val[p])p=rs[p];
else ans=val[p],p=ls[p];
}
}int rnk(int v){
int x=0,y=0,ans=0;
split(R,v-1,x,y);ans=siz[x]+1;
return R=merge(x,y),ans;
}
}using namespace FHQTreap;