0. 前置知识：\(treap\)的定义
树堆，在数据结构中也称Treap，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。
>——摘自百度百科
形象化一点：
- \(treap\)是关于\(val\)的二叉搜索树
- \(treap\)是关于\(（随机权值）rdm（随机权值）\)的二叉搜索树
为了满足上面两条性质，就要分情况对\(treap\)进行旋转
怎么转我也不会……因为这是介绍\(fhq\) \(treap\)的文章
1.\(fhq\) \(treap\)
基本定义&操作
解释下数组含义
int son[N][2]; //0：左儿子 1：右儿子
int sz[N];//子树大小
int val[N];//权值
int rdm[N];//随机权值
int cnt;//总treap的节点个数如何开一个新节点
int new_node(int x) {
val[++cnt]=x;//节点权值
rdm[cnt]=rand();//随机权值
sz[cnt]=1;//子树大小
return cnt;
}\(pushup\)
inline void pushup(int x) {
sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;
}核心操作
\(fhq\) \(treap\)的核心操作只有两种：\(split\)和\(merge\)，这两种操作巧妙玄学地让每次插入和删除，\(treap\)的性质都不会被破坏，自然也就不用旋转
\(merge\)
把a、b两棵\(treap\)合成一棵大\(treap\)的操作
满足a所有节点的权值 < b所有节点的权值
这样就只用维护随机权值的\(heap\)性质
代码：
void merge(int &now,int x,int y) { //分别为根节点地址，a,b
if(!x || !y) {
now=x+y;
return;
}
if(rdm[x]<rdm[y]) { //维护rdm堆
now=x;//保留a的左子树
merge(son[now][1],son[now][1],y);//把b塞进a的右子树，维护bst
}else { //原理同上
now=y;
merge(son[now][0],x,son[now][0]);
}
pushup(now);
}\(split\)
把一棵大\(treap\)按照某种划分标准分成\(a\)、\(b\)两棵\(treap\)的操作
常用的划分标准有权值\(val\)和子树大小\(sz\)，两种代码都会给
代码：
- 按val划分
//划分后，a中所有元素<=k，b中所有元素>k
void split(int now,int k,int &x,int &y) {//分别为：当前节点,划分标准,a的树根,b的树根
if(!now) {//没东西了
x=y=0;
return;
}
if(val[now]<=k) {//利用bst的性质
x=now;
split(son[now][1],k,son[now][1],y);
}else {
y=now;
split(son[now][0],k,x,son[now][0]);
}
pushup(now);
}- 按sz划分
//把大treap中前k小的元素放到a中，剩下放到b中
void split(int now,int k,int &x,int &y) {
if(!now) {//没东西了
x=y=0;
return;
}
if(sz[son[now][0]]>k) {
x=now;
split(son[now][1],k-sz[son[now][0]]-1,son[now][1],y);
}else {
y=now;
split(son[now][0],k,x,son[now][0]);
}
pushup(now);
}2.模板题
洛谷 3369/BZOJ 3224/Tyvj 1728 普通平衡树
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int root=0;
struct fhq_treap {
int son[N][2],sz[N],val[N],rdm[N],cnt;
inline int new_node(int x) {
val[++cnt]=x,rdm[cnt]=rand(),sz[cnt]=1;
return cnt;
}
inline void pushup(int x) {
sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;
}
void split(int now,int k,int &x,int &y) {
if(!now) {
x=y=0;
return;
}
if(val[now]<=k) {
x=now;
split(son[now][1],k,son[now][1],y);
}else {
y=now;
split(son[now][0],k,x,son[now][0]);
}
pushup(now);
}
void merge(int &now,int x,int y) {
if(!x || !y) {
now=x+y;
return;
}
if(rdm[x]<rdm[y]) {
now=x;
merge(son[now][1],son[now][1],y);
}else {
now=y;
merge(son[now][0],x,son[now][0]);
}
pushup(now);
}
void kth(int now,int k) {//第k大数
while(1) {
if(sz[son[now][0]]>=k) {
now=son[now][0];
}else {
if(sz[son[now][0]]+1==k) break;
k-=(sz[son[now][0]]+1);
now=son[now][1];
}
}
printf("%d\n",val[now]);
}
}T;
int main() {
int n,op,x,a,b,c;
scanf("%d",&n);
T.sz[0]=0;
T.cnt=0;
while(n--) {
a=0,b=0;
scanf("%d%d",&op,&x);
if(op==1) { //插入x数
T.split(root,x,a,b);
int t=T.new_node(x);
T.merge(a,a,t);
T.merge(root,a,b);
}
if(op==2) { //删除x数
T.split(root,x,a,b);
T.split(a,x-1,a,c);
T.merge(c,T.son[c][0],T.son[c][1]);
T.merge(a,a,c);
T.merge(root,a,b);
}
if(op==3) { //查询x数的排名
T.split(root,x-1,a,b);
printf("%d\n",T.sz[a]+1);
T.merge(root,a,b);
}
if(op==4) { //查询排名为x的数
T.kth(root,x);
}
if(op==5) { //求x的前驱
T.split(root,x-1,a,b);
T.kth(a,T.sz[a]);
T.merge(root,a,b);
}
if(op==6) { //求x的后继
T.split(root,x,a,b);
T.kth(b,1);
T.merge(root,a,b);
}
}
}洛谷 3391 文艺平衡树
这题只有区间翻转操作，所以不用考虑那么多有的没的.
可以把每个点的编号看作权值。假设要翻转区间\([l,r]\)，先把\([l,r]\)这个区间分裂出来，打个标记，下传维护时直接\(swap(lson,rson)\)就行了
然而这样会破坏\(treap\)的性质，所以还有区间\(k\)大的话不能直接查
能写\(splay\)尽量写\(splay\)吧，\(fhq\) \(treap\)常数有点大……
#include <bits/stdc++.h>
#define N 100010
using namespace std;
int root=0;
struct fhq_treap{
#define lson son[now][0]
#define rson son[now][1]
int rdm[N],val[N],w[N],sz[N],son[N][2],cnt=0;
bool tag[N];//翻转的lazytag
int NewNode(){
val[++cnt]=cnt,rdm[cnt]=rand(),sz[cnt]=1,tag[cnt]=0;
return cnt;
}
void pushup(int now){sz[now]=sz[lson]+sz[rson]+1; }
void pushdown(int now){
swap(lson,rson);
if(lson) tag[lson]^=1;
if(rson) tag[rson]^=1;
tag[now]=0;
}
void merge(int &now,int x,int y){
if(!x || !y){
now=x+y;
return;
}
if(rdm[x]<rdm[y]){
if(tag[x]) pushdown(x);
now=x,merge(rson,rson,y);
}
else{
if(tag[y]) pushdown(y);
now=y,merge(lson,x,lson);
}
pushup(now);
}
void split(int now,int k,int &x,int &y){
if(!now){
x=y=0;
return;
}
if(tag[now]) pushdown(now);
if(sz[lson]+1<=k) x=now,split(rson,k-sz[lson]-1,rson,y);
else y=now,split(lson,k,x,lson);
pushup(now);
}
void print(int now){//中序遍历输出答案
if(!now) return;
if(tag[now]) pushdown(now);
print(lson);
printf("%d ",val[now]);
print(rson);
}
}T;
int main(){
int n,m,l,r,i;
int a=0,b=0,c=0;
scanf("%d",&n);
for(i=1;i<=n;++i){
int x=T.NewNode();
T.merge(root,root,x);
}
scanf("%d",&m);
while(m--){
a=0,b=0,c=0;
scanf("%d%d",&l,&r);
T.split(root,l-1,a,b);
T.split(b,r-l+1,b,c);
T.tag[b]^=1;
T.merge(b,b,c),T.merge(root,a,b);
}
T.print(root);
}