平衡树！（Fhq-Treap和Splay）
White_Wat
·
2023-12-26 22:40:30
·
算法·理论
所以没人看我为什么要写啊是因为我要用来复习啊那没事了
Fhq Treap 普通平衡树
Treap = Tree + Heap
即 Treap 是同时满足二叉堆 Heap 和二叉搜索树的平衡树
满足 Heap 的堆值随机来使得平衡树的状态随机（大概率不会退化成链）
大部分操作代码里都打注释了（不会就看AgOH的讲解）
（算了还是讲一下吧）
Fhq Treap 就是一种不用旋转的平衡树，时间复杂度 O(n log n)。
因为其不旋转（使用分裂和合并替代）但却能保持 Treap 的性质，使其思想复杂度 大大减小！
维护 Fhq Treap 的有两个主要操作，分裂和旋转：
分裂
就是一整棵树裂开来
分裂操作分两种：按值分裂和按大小分裂，按大小分裂文艺平衡树里再说。
按值分裂即将一颗树按照给定值 x 分成两颗树，也就是两颗小 Treap ，一颗树上的所有值都 \le val ，另一颗树上所有值都 > val 。
合并
就是将两棵树合并成为一颗树。因为合并时树 x 里的值都小于树 y 里的值，所以合并时就可以用二叉堆的性质和二叉搜索树的性质使得合并操作如代码所示，注释挺详细了捏~
那接下来就是利用分裂与合并来进行平衡树操作，例题是- P3369 【模板】普通平衡树。~（代码里都有注释了那这里就偷懒不写了）~
下面是全是注释的代码（好丑要被嫌弃了）
还有就是代码细节很多写的时候不要漏掉+1-1什么的（难道只有我太蒻了每次写都会出错O.o）
#include
#include
using namespace std;
const int N=1e5+5;
struct node{
int l,r; //左右子树
int val,key;//值和索引，索引用于模拟二叉堆
int size; //子树大小
}fhq[N];
int cnt,root; //这里是树的大小和根节点
mt19937 rnd(210828); //幸运随机码
inline int newnode(int val)
{
fhq[++cnt].val=val; //这个不用解释了吧...
fhq[cnt].key=rnd(); //随机索引！
fhq[cnt].size=1; //最开始的时候树的大小肯定是1捏~
return cnt; //每次返回新创建的节点编号，方便合并
}
//这个是用来更改树大小的捏~
inline void update(int now)
{
fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
//树的值 <= val 归 一棵树 (x)
//树的值 > val 归 另一棵树 (y)
/*
虽然是分裂成树x与是y，但是传入的x与y可以说是当前节点now
在分裂后可以与树x或者树y连接的编号捏~
*/
inline void split(int now,int val,int &x,int &y)
{
if(!now) x=y=0;
else
{
if(fhq[now].val<=val)
{
x=now; //根据搜索二叉树定义此时所有的左子树val都 <=val，所以分裂右子树
split(fhq[now].r,val,fhq[now].r,y); //分裂右子树
}
else
{
y=now; //根据搜索二叉树定义此时所有的右子树val都 >val，所以分裂左子树
split(fhq[now].l,val,x,fhq[now].l); //分裂左子树
}
update(now);//修改树大小
}
}
//树x中所有值都<=树y中所有值（这个在传入时就要注意捏~）
inline int merge(int x,int y)
{
if(!x||!y) return x+y; //如果x或者y不存在就返回另外一个
if(fhq[x].key>fhq[y].key) //索引随机，符号可以是 任意 ( > >= < <= )
//所以这里是类似大根堆
{
/*
树x的根在树y根的上方
因为树x中的值小于树y中的值，所以树y一定在树x的右方
所以树y在树x的右下方
所以是树x右子树和y合并
*/
fhq[x].r=merge(fhq[x].r,y); //传入的树值第一个小第二个大
update(x); //更新新的树大小
return x;
}
else
{
/*
树x的根在树y根的下方
因为树x中的值小于树y中的值，所以树y一定在树x的右方
所以树y在树x的右上方
所以是树x和树y左子树合并
*/
fhq[y].l=merge(x,fhq[y].l);
update(y); //更新新的树大小
return y;
}
}
/*
插入操作：
先按照值val分裂成树x和树y
合并时要满足前参<=后参
所以先合并树x和新节点，再与y树合并
*/
int x,y,z;
inline void ins(int val)
{
split(root,val,x,y);
root=merge(merge(x,newnode(val)),y);
}
/*
删除操作：
先按照值val分裂成树x和树z
再按照值val-1分裂树x成树x和树y
现在树y上值全为val
去掉树y根节点即可（合并树y左子树和右子树）
*/
inline void del(int val)
{
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(fhq[y].l,fhq[y].r);
root=merge(merge(x,y),z);
}
/*
查询排名操作：
先按照val-1分裂成树x和树y
此时val的排名就是树x的大小+1( fhq[x].size+1 )
*/
inline void get_rank(int val)
{
split(root,val-1,x,y);
printf("%d\n",fhq[x].size+1);
root=merge(x,y);
}
/*
查询排名的值：
从根节点开始
如果左子树的大小大于等于排名，那么就在左子树上找
如果左子树大小+1等于排名，那么就是当前结点
否则就是在右子树，是右子树里排名为[当前排名 - (左子树大小+1)]
（这个多减去的1是算上当前节点排名）
*/
inline void get_num(int rank)
{
int now=root;
while(now)
{
if(fhq[fhq[now].l].size+1==rank)
break;
else if(fhq[fhq[now].l].size>=rank)
now=fhq[now].l;
else
{
rank-=fhq[fhq[now].l].size+1;//在右子树的排名为[当前排名 - (左子树大小+1)]
now=fhq[now].r;
}
}
printf("%d\n",fhq[now].val);
}
/*
找前驱(比当前数小的最大的数):
按照val-1分裂成树x和树y
树x中最右边的数为最大值
*/
inline void pre(int val)
{
split(root,val-1,x,y);
int now=x;
while(fhq[now].r)
now=fhq[now].r;
printf("%d\n",fhq[now].val);
root=merge(x,y);
}
/*
找后继(比当前数大的最小的数):
按照val分裂成树x和树y
树y中最左边的数为最小值
*/
inline void nxt(int val)
{
split(root,val,x,y);
int now=y;
while(fhq[now].l)
now=fhq[now].l;
printf("%d\n",fhq[now].val);
root=merge(x,y);
}
int n;
int main()
{
scanf("%d",&n);
while(n--)
{
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1)
ins(x);
else if(opt==2)
del(x);
else if(opt==3)
get_rank(x);
else if(opt==4)
get_num(x);
else if(opt==5)
pre(x);
else if(opt==6)
nxt(x);
}
return 0;
}
文艺平衡树
（先等我看懂）
你说的对，但是文艺平衡树我还是不知道要怎么说所以先代码上来，让我再看看
#include
#include
using namespace std;
const int N=1e5+5;
struct node{
int l,r;
int val,key;
int size;
bool reverse; //翻转懒标记
}fhq[N];
int cnt,root;
mt19937 rnd(210828);
inline int newnode(int val)
{
fhq[++cnt].val=val;
fhq[cnt].key=rnd();
fhq[cnt].size=1;
return cnt;
}
inline void update(int now)
{
fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
inline void pushdown(int now) //下传懒标记
{
swap(fhq[now].l,fhq[now].r);
fhq[fhq[now].l].reverse^=1;
fhq[fhq[now].r].reverse^=1;
fhq[now].reverse=0;
}
//文艺平衡树是按照树的大小分裂
void split(int now,int siz,int &x,int &y)
{
if(!now) x=y=0;
else
{
if(fhq[now].reverse) pushdown(now);
if(fhq[fhq[now].l].size { x=now; split(fhq[now].r,siz-fhq[fhq[now].l].size-1,fhq[now].r,y); } else { y=now; split(fhq[now].l,siz,x,fhq[now].l); } update(now); } } int merge(int x,int y) { if(!x||!y) return x+y; if(fhq[x].key>fhq[y].key) { if(fhq[x].reverse) pushdown(x); fhq[x].r=merge(fhq[x].r,y); update(x); return x; } else { if(fhq[y].reverse) pushdown(y); fhq[y].l=merge(x,fhq[y].l); update(y); return y; } } //反转操作 void reverse(int l,int r) { int x,y,z; split(root,l-1,x,y); split(y,r-l+1,y,z); fhq[y].reverse^=1; root=merge(merge(x,y),z); } void ldr(int now) { if(!now) return ; if(fhq[now].reverse) pushdown(now); ldr(fhq[now].l); printf("%d ",fhq[now].val); ldr(fhq[now].r); } int n,m; int main() { cin>>n>>m; for(int i=1;i<=n;i++) root=merge(root,newnode(i)); while(m--) { int l,r; cin>>l>>r; reverse(l,r); } ldr(root); return 0; } Splay （几天集训学的初三下册没时间先丢代码） #include using namespace std; const int N = 100010; int n,opt,x; int root,tot; struct Splay{ int fa,siz,ch[3],val,cnt; }t[N]; void maintain(int x){ t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt; }//维护 bool get(int x){ return x==t[t[x].fa].ch[1]; }//判断当前节点是左儿子还是右儿子 void clear(int x){ t[x].ch[0]=t[x].ch[1]=t[x].fa=t[x].val=t[x].siz=t[x].cnt=0; }//删除当前节点 void rotate(int x){ int y=t[x].fa,z=t[y].fa,lor=get(x); t[y].ch[lor]=t[x].ch[lor^1]; if(t[x].ch[lor^1]) t[t[x].ch[lor^1]].fa=y; t[x].ch[lor^1]=y; t[y].fa=x; t[x].fa=z; if(z) t[z].ch[y==t[z].ch[1]]=x; maintain(y),maintain(x); }//旋转x节点，好麻烦啊自己看自己推一下吧 //使用次数最多的 Splay 树的主要函数 void splay(int x){ while(t[x].fa){ int f=t[x].fa; if(t[f].fa) rotate(get(x)==get(f)?f:x); rotate(x); }//如果在同一条直链上就先旋转父亲节点，否则就直接旋转当前节点 root=x; }//将x旋转为根节点，每次操作或者询问完都要把操作过的放到树根 void ins(int x){ if(!root){ t[++tot].val=x; t[tot].cnt++; root=tot; maintain(root); return ; }//没有树根那就放进去呗~ int now=root,f=0; while(1){ if(t[now].val==x) { t[now].cnt++; maintain(now); splay(now);//必然操作捏~ break; }//如果当前节点是要插入的数 f=now; now=t[now].ch[t[now].val if(!now){ t[++tot].val=x; t[tot].cnt++; t[tot].fa=f; t[f].ch[t[f].val maintain(tot); splay(tot);//必然操作捏~ break; }//找不到值为x的点就插入 } } int get_rank(int x){ int rank=0,now=root; while(1) { if(x now=t[now].ch[0]; } else{ rank+=t[t[now].ch[0]].siz; if(x==t[now].val){ splay(now);//必然操作捏~ return rank+1; } rank+=t[now].cnt; now=t[now].ch[1]; } } } int get_num(int rank){ int now=root; while(1){ if(t[now].ch[0]&&t[t[now].ch[0]].siz>=rank){ now=t[now].ch[0]; } else{ rank-=t[now].cnt+t[t[now].ch[0]].siz; if(rank<=0){ splay(now);//就是必然操作捏！~ return t[now].val; } now=t[now].ch[1]; } } } int pre(){ int now=t[root].ch[0]; if(!now) return now; while(t[now].ch[1]) now=t[now].ch[1]; splay(now);//拉到根上 return now; }//前驱是左子树中最右边的节点 int nxt(){ int now=t[root].ch[1]; if(!now) return now; while(t[now].ch[0]) now=t[now].ch[0]; splay(now);//拉到根上 return now; }//后继是右字数中最左边的节点 void del(int x){ get_rank(x);//将要修改的数放到根节点 if(t[root].cnt>1){ t[root].cnt--; maintain(root); return ; }//要删除的节点有多个那么就把其中一个删去 if(!t[root].ch[0]&&!t[root].ch[1]){ clear(root); root=0; return ; }//只有一个根节点时就直接删去 if(!t[root].ch[0]){ int now=root; root=t[root].ch[1]; t[root].fa=0; clear(now); return ; }//哭了没有左儿子，那么就把右儿子拉上来 if(!t[root].ch[1]){ int now=root; root=t[root].ch[0]; t[root].fa=0; clear(now); return ; }//哭了没有右儿子，那么就把左儿子拉上来 //太棒了如果有两个儿子的话就合并 int now=root; int p=pre();//找前驱 t[t[now].ch[1]].fa=p;//右子树的 baba 就是 p 啦~ t[p].ch[1]=t[now].ch[1];//x 的儿子就是右子树啦~ clear(now);//删掉咯~ maintain(root);//因为前边是要找前驱所以现在 p 才是根啦~ } int main() { cin>>n; while(n--) { cin>>opt>>x; if(opt==1) ins(x); else if(opt==2) del(x); else if(opt==3)//这里错了划重点 ins(x),cout< else if(opt==4) cout< else if(opt==5)//查找前驱后继都不太一样 ins(x),cout< else ins(x),cout< } return 0; }