前言
首先 sto fhq orz。
以前有一篇[链接登录后可见]，但是只讲了 BST 和 Splay（还没有讲全）。今天补一补 神·fhq 发明的 fhqTreap。
关于 fhqTreap
fhqTreap 又称为 无旋Treap。顾名思义，就是 “不用旋转的Treap”。
fhqTreap 仅仅使用 分裂（split） 和 合并（merge）来支持其他平衡树拥有的操作。
fhqTreap 详解
操作数据 $\verb! (data)!$
...
const int N=1e5+10;
...
private:
#define lc(rt) son[rt][0]
#define rc(rt) son[rt][1]
int cnt=0;
int a[N], sz[N], rk[N], son[N][2];
...
public:
int root=0;
...
...
$\verb!def: lc(rt) :=son[rt][0]!$：左儿子。
$\verb!def: rc(rt) :=son[rt][1]!$：右儿子。
$\verb!var: cnt !$：结点数。
$\verb!arr: a[N] !$：结点的值。
$\verb!arr: sz[N] !$：以结点为根的子树大小。
$\verb!arr: rk[N] !$：结点的优先级。
$\verb!var: root !$：……
新建结点 操作 $\verb! (node)!$
根据定义自行理解。
int node(int val){
sz[++cnt]=1;
a[cnt]=val;
rnk[cnt]=rand();
return cnt;
}
合并 操作 $\verb! (merge)!$
$\verb!merge!$ 操作就是合并一下根节点和新建节点 然后保留根/替换根（$rk$ 决定）
反正是随机合并 期望树高 $\log n$。
int merge(int x, int y){
if(!x||!y) return x|y;//空树
//根据 rk 决定
if(rnk[x]<rnk[y]){
rc(x)=merge(rc(x),y);
pushup(x);
return x;
}
else{
lc(y)=merge(x,lc(y));
pushup(y);
return y;
}
}
分裂 操作 $\verb! (split)!$
$\verb!split!$ 实现的操作大概是 把一棵树分成俩…然后左边的值小于等于 $val$ 右边的值大于 $val$。
如果你 split(rt,val,x,y)
那么你就把 $rt$ 分成两个部分 $x,y$ 了 其中 $x$ 的子树的 $v_x\leq val$ ， $y$ 的子树的 $v_y>k$。
void split(int rt, int val, int& x, int& y){
if(!rt){x=y=0;return;}//空
//根据 val 决定
if(a[rt]<=val){
x=rt;
split(rc(x),val,rc(x),y);
}
else{
y=rt;
split(lc(y),val,x,lc(y));
}
pushup(rt);//记得更新
}
查找第 $k$ 小 $\verb! (kth)!$
可以按照 $sz$ 来找 $\operatorname{kth}$。 递归/非递归都行。
int kth(int rt, int k){
if(k<=sz[lc(rt)]) return kth(lc(rt),k);
if(sz[lc(rt)]+1==k) return a[rt];
return kth(rc(rt),k-sz[lc(rt)]-1);
}
查找排名为 $x$ 的数 $\verb! (rnk)!$
$\verb!rank!$ 的话就分离一个 $val=k-1$ 的子树。然后求这个子树的 $sz$ 就知道 $\verb!rank!$ 了。
int rnk(int val){
int x, y, res;
split(root,val-1,x,y);
res=sz[x]+1;
root=merge(x,y);
return res;
}
其他操作
和 $\verb!rnk!$ 差不多，不讲了。
代码实现
$$\verb!Class !\operatorname{fhq}.$$
class fhq{
private:
#define lc(rt) son[rt][0]
#define rc(rt) son[rt][1]
int cnt=0;
int a[N], sz[N], rnk[N], son[N][2];
//新建结点
int node(int val){
sz[++cnt]=1;
a[cnt]=val;
rnk[cnt]=rand();
return cnt;
}
void pushup(int rt){
sz[rt]=sz[lc(rt)]+sz[rc(rt)]+1;}
//按照BST的性质合并
int merge(int x, int y){
if(!x||!y) return x|y;
if(rnk[x]<rnk[y]){
rc(x)=merge(rc(x),y);
pushup(x);
return x;
}
else{
lc(y)=merge(x,lc(y));
pushup(y);
return y;
}
}
//将rt分裂成x和y (其中vx<=val,vy>val)
void split(int rt, int val,
int& x, int& y){
if(!rt){x=y=0;return;}
if(a[rt]<=val){
x=rt;
split(rc(x),val,rc(x),y);
}
else{
y=rt;
split(lc(y),val,x,lc(y));
}
pushup(rt);
}
public:
int root=0;
//插入一个点
void insert(int val){
int x, y;
split(root,val,x,y);
root=merge(merge(x,node(val)),y);
}
void erase(int val){
int x, y, z;
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(lc(y),rc(y));
root=merge(merge(x,y),z);
}
int kth(int rt, int k){
if(k<=sz[lc(rt)])
return kth(lc(rt),k);
if(sz[lc(rt)]+1==k) return a[rt];
return kth(rc(rt),k-sz[lc(rt)]-1);
}
int ranks(int val){
int x, y, res;
split(root,val-1,x,y);
res=sz[x]+1;
root=merge(x,y);
return res;
}
int pre(int val){
int x, y, res;
split(root,val-1,x,y);
res=kth(x,sz[x]);
root=merge(x,y);
return res;
}
int suf(int val){
int x, y, res;
split(root,val,x,y);
res=kth(y,1);
root=merge(x,y);
return res;
}
}t;
练习题：[链接登录后可见]
