前言
原来世上还有这么简短的平衡树……
——XiaoZi_qwq
参考资料：Konjac 的文章
正文
fhq Treap 的核心操作是 spilt 和 merge。其他的普通平衡树差不多
分裂
分裂有两种裂法：
-
把权值小于等于 \(k\) 的分裂出去；
-
把前 \(k\) 个分裂出去；
这里只展示后者：
void spilt(int i,int& x,int& y,int k){if(!i){x=y=0;return;}push_down(i);if(k>sz[ch[i][0]])x=i,spilt(ch[i][1],ch[x][1],y,k-sz[ch[i][0]]-1);elsey=i,spilt(ch[i][0],x,ch[y][0],k);push_up(i);
}
很优美qwq。
合并
和线段树合并差不多，只不过是在钦定返回哪个点是需要依靠随机值。合并是有顺序的，左边是权值小的，右边是权值大的。
int merge(int x,int y){if(!x || !y) return x+y;push_down(x),push_down(y);if(rd[x]<rd[y]){ch[x][1]=merge(ch[x][1],y);push_up(x);return x;}ch[y][0]=merge(x,ch[y][0]);push_up(y);return y;
}
插入，删除
- 插入就是把权值小于插入点权值的点分裂出去，再按顺序合并起来；
- 删除就是把权值小于删除点权值的点和权值大于删除点权值的点依次分裂出去，合并删除点左右儿子后，最后按顺序合并起来；
查前驱、后继、排名……
- 查前驱就是把权值小于自己的点分裂出去，并在分裂出的树上一直跳右儿子；
- 查后继就是把权值大于自己的点分裂出去，并在分裂出的树上一直跳左儿子；
- 查排名就是把权值小于自己的点分裂出去，分裂出的树的大小加一就是排名；
区间操作
把这个区间对于的树分裂出来就行，操作完再按顺序合并回去就行。
void rev(int l,int r){int rt1,rt2,rt3,rt4;rt1=rt2=rt3=rt4=0;spilt(rt,rt1,rt2,l-1);spilt(rt2,rt3,rt4,r-l+1);upd(rt3);rt=merge(rt1,merge(rt3,rt4));
}