[关闭]
@xzyxzy 2018-04-01T09:11:42.000000Z 字数 9215 阅读 1881

伸展树(Splay)

数据结构

一、基本内容

yyb博客：http://www.cnblogs.com/cjyyb/p/7499020.html
基本类型：平衡树（树深度期望是log的）二叉搜索树（中序遍历为从小到大）
核心思想：不断把查询过的点转到根，尽可能打乱顺序使其尽量接近期望复杂度
(萝卜说研究表明90%的询问都集中在10%的数据中，所以Splay十分难被卡)

二、题目

1、练基础

2、刷提高

3、变态题

三、做题经验

1、支持的操作

对于点

A、插/删点

详见后方区间操作

B、动态查询某数(结点)前驱后继

用Next函数实现，原理是把需要查询的数转到根，再在其右子树的最左端查后继，左子树的最右段查前驱

C、查询排名为k的数/查询k的排名

k的排名那么把k转到根，左子树大小便是k的排名，见代码110-120行，很好理解

对于区间

每次将要访问到儿子结点的时候都要pushdown！！

A、插/删区间

把要插入的位置的前一个数绕到根，后一个数绕到根的右儿子，然后把插入的区间建成一棵splay连到后一个数的左儿子上
用的前驱转到根，后继转到前驱的儿子，然后后继的左儿子那一段就是要删的点，直接去掉

B、区间翻转

翻转一个区间，颠覆了Splay按权值排序的概念
具体操作就是翻转一个区间，相当于把所有结点的左右儿子交换
那么打一个标记，当要修改时pushdown就好了(好像和线段树了懒标记有点像哦)
建议把标记定义成已经翻转了该点的左右儿子！这里是模板！这里有难题！

C、区间覆盖

D、区间求和

E、求数列最大子段和

详见下方维护数列的code

F、区间加法

自己yy一下应该可以弄出来

由此可见，splay可以代替线段树的所有操作！
但是，越通用的算法常数越大！
大致可以理解为 splay>线段树>树状数组

还有呢

Splay合并

这个嘛不太好说，启发式合并好了，梦幻布丁和永无乡都是的

Splay模板

  1. //https://www.luogu.org/problemnew/show/P3369
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. using namespace std;
  7. int read()
  8. {
  9.     char ch=getchar();
  10.     int h=0,t=1;
  11.     while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
  12.     if(ch=='-'){ch=getchar();t=-1;}
  13.     while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  14.     return h*t;
  15. }
  16. int n,tot,root;
  17. struct Splay{int fa,val,cnt,siz,ch[2];}t[100011];
  18. void pushup(int x)
  19. {
  20.     t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
  21. }
  22. void rotate(int x)//把x的父亲变成它儿子
  23. {
  24.     int y=t[x].fa,z=t[y].fa;
  25.     int k=t[y].ch[1]==x;//表示x是y的 0左儿子 1右儿子
  26.     //Step1 把x和z相连(相同)
  27.     t[z].ch[t[z].ch[1]==y]=x;//y位置
  28.     t[x].fa=z;
  29.     //Step2 把x的儿子丢给y(相反)
  30.     t[y].ch[k]=t[x].ch[k^1];
  31.     t[t[x].ch[k^1]].fa=y;
  32.     //Step3 把y搞成x的儿子(相反)
  33.     t[x].ch[k^1]=y;
  34.     t[y].fa=x;
  35.     pushup(y);//更新！！
  36.     //注意顺序！！！！！
  37. }
  38. void splay(int x,int fa)//把x旋转成fa的儿子(fa=0则旋转到根)
  39. {
  40.     while(t[x].fa!=fa)
  41.     {
  42.         int y=t[x].fa,z=t[y].fa;
  43.         if(z!=fa)(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
  44.         rotate(x);
  45.     }
  46.     if(!fa)root=x;
  47.     pushup(x);//更新！！(放在这里常数会小些)
  48.     /*
  49.       这是重点！敲黑板！
  50.       把x旋转到根，这一步保证了双旋，近似可以理解为rand了一下链(可以自己画一下单旋，会发现单旋的旧链没有改变，复杂度会被卡)于是这样之后更接近了期望复杂度NlogN
  51.       双旋要求x祖父不是将要成为x父亲的结点(如果是的而且旋转了y那么z成为y儿子，x永远无法成为z的儿子),而且当从祖父到x一直是左儿子或者一直是右儿子就可以转y了,并且每一步最后都必须动x,在前面选择的时候，如果不同时为左儿子或右儿子，那么动y并不会将x向上提，没有效果
  52.       在每一步最后，如果不动x而是一直动y，那么y上方的旧链会出现在y右儿子的左儿子上
  53.       每一步都是精心打造，目的是让树尽可能随机重构，来平衡其期望复杂度,如果有任何疑问，手玩一棵Splay就会发现去掉某一句都会使Splay出现旧链或效率变低
  54.     */
  55. }
  56. void Insert(int num)//把num加入Splay树
  57. {
  58.     int x=root,fa=0;
  59.     while(x&&t[x].val!=num)
  60.     {
  61.         fa=x;//向下找
  62.         x=t[x].ch[num>t[x].val];//大于向右，小于向左
  63.     }
  64.     if(x){t[x].cnt++;splay(x,0);return;}//新点非根
  65.     x=++tot;
  66.     if(fa)t[fa].ch[num>t[fa].val]=x;
  67.     t[x]=(Splay){fa,num,1,1,{0,0}};
  68.     splay(x,0);//把当前位置移到根，保证结构的平衡
  69.     //还有一个作用，更新了x的树大小，那么要一路更新上去
  70. }
  71. void find(int num)//找到num的位置并把它旋转到根
  72. {
  73.     int x=root;if(!x)return;
  74.     while(t[x].ch[num>t[x].val]&&num!=t[x].val)
  75.         x=t[x].ch[num>t[x].val];
  76.     splay(x,0);//旋转到根
  77. }
  78. int Next(int num,int f)//查找num的前驱(0)或后继(1)
  79. {
  80.     find(num);int x=root;
  81.     if(t[x].val>num&&f)return x;//当前结点大于x且查询后继
  82.     if(t[x].val<num&&!f)return x;//当前结点小于x且查询前驱
  83.     x=t[x].ch[f];//后继在右子树，前驱在左子树
  84.     while(t[x].ch[f^1])x=t[x].ch[f^1];//反着找
  85.     return x;
  86. }
  87. void Delete(int num)//删除num(同理也可以删除区间)
  88. {
  89.     int last=Next(num,0),next=Next(num,1);
  90.     splay(last,0);splay(next,last);
  91.     //查找l的前驱和r的后继，把前驱转到根，后继转到根的下面
  92.     //那么l到r这段区间里所有数就是在后继的左儿子上了
  93.     int pos=t[next].ch[0];
  94.     if(t[pos].cnt>1)
  95.     {
  96.         t[pos].cnt--;
  97.         splay(pos,0);
  98.     }
  99.     else
  100.     {
  101.         t[next].ch[0]=0;//丢掉！
  102.         pushup(next);pushup(last);//要记得更新呦～
  103.     }
  104. }
  105. int Query1Rank(int num)//查找num的编号
  106. {
  107.     find(num);
  108.     return t[t[root].ch[0]].siz;
  109. }
  110. int Query2Rank(int num)//查找编号为num的数
  111. {
  112.     int x=root;if(t[x].siz<num)return 0;
  113.     while(1)
  114.     {
  115.         int Size=t[t[x].ch[0]].siz,Cnt=t[x].cnt;
  116.         if(num>Size&&num<=Size+Cnt)return t[x].val;
  117.         if(num<=Size)x=t[x].ch[0];
  118.         if(num>Size+Cnt){num-=Size+Cnt;x=t[x].ch[1];}//注意顺序
  119.     }
  120. }
  121. int main()
  122. {
  123.     n=read();
  124.     Insert(+2147483647);
  125.     Insert(-2147483647);//便于找到前驱后继
  126.     for(int i=1;i<=n;i++)
  127.     {
  128.         int opt=read(),x=read();
  129.         if(opt==1){Insert(x);}
  130.         if(opt==2){Delete(x);}
  131.         if(opt==3){printf("%d\n",Query1Rank(x));}
  132.         if(opt==4){printf("%d\n",Query2Rank(x+1));}
  133.         if(opt==5){printf("%d\n",t[Next(x,0)].val);}
  134.         if(opt==6){printf("%d\n",t[Next(x,1)].val);}
  135.     }
  136.     return 0;
  137. }

维护数列

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<queue>
  5. #include<cstring>
  6. #define RG register 
  7. using namespace std;
  8. inline int read()
  9. {
  10.     RG char ch=getchar();
  11.     RG int h=0,t=1;
  12.     while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
  13.     if(ch=='-'){t=-1;ch=getchar();}
  14.     while(ch>='0'&&ch<='9'){h=(h<<3)+(h<<1)+ch-'0';ch=getchar();}
  15.     return h*t;
  16. }
  17. const int MAXN=500100;
  18. int N,M,root,tot;
  19. struct Splay
  20. {
  21.     int val,fa,siz,ch[2];
  22.     int sum,lx,rx,mx;
  23.     bool mark,lazy; 
  24.     //bool u;
  25. }t[MAXN];
  26. queue<int>Q;//内存池
  27. int pos,all,c;
  28. int a[MAXN],zhan[MAXN],top;
  29. /*
  30. inline void Printtree()
  31. //功能：调试输出Splay
  32. {
  33.     tot=0;
  34.     printf("root=%d\n",root);
  35.     for(RG int i=1;i<=MAXN-1;i++)
  36.         if(t[i].u)
  37.             tot++,printf("#%2d: fa=%2d,siz=%2d,mark=%2d,lazy=%2d,val=%2d,sum=%2d,lc=%2d,rc=%2d,lx=%2d,rx=%2d,mx=%2d\n",i,t[i].fa,t[i].siz,t[i].mark,t[i].lazy,t[i].val,t[i].sum,t[i].ch[0],t[i].ch[1],t[i].lx,t[i].rx,t[i].mx);
  38.     printf("tot=%d\n",tot);
  39. }
  40. */
  41. inline Splay Get(RG int v,RG int f,RG int u)
  42. //功能：见下，初始化一个结点
  43. {
  44.     RG Splay R;
  45.     R.val=v;R.fa=f;R.siz=u;R.ch[0]=0;R.ch[1]=0;
  46.     R.mark=0;R.lazy=0;R.sum=v;
  47.     R.lx=max(0,v);R.rx=max(0,v);R.mx=u?v:-1e9;
  48.     //R.u=u;
  49.     return R;
  50. }
  51. inline void pushup(RG int x)
  52. //功能：由下往上更新x结点的一些内容
  53. {
  54.     t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
  55.     t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].val;
  56.     t[x].lx=max(t[t[x].ch[0]].lx,t[t[x].ch[0]].sum+t[x].val+t[t[x].ch[1]].lx);
  57.     t[x].rx=max(t[t[x].ch[1]].rx,t[t[x].ch[1]].sum+t[x].val+t[t[x].ch[0]].rx);
  58.     t[x].mx=max(max(t[t[x].ch[0]].mx,t[t[x].ch[1]].mx),t[t[x].ch[0]].rx+t[x].val+t[t[x].ch[1]].lx);
  59.     //留坑:当一个点没有右儿子然后mx必须为负数的时候，由此程序跑出来mx=0，但已通过的程序大部分都没判，故留坑
  60. }
  61. inline void pushdown(RG int x)
  62. //功能：由上往下下放一些标记
  63. {
  64.     if(t[x].lazy)//lazy表示已经改变了当前结点的值
  65.     {
  66.         t[x].lazy=0;t[x].mark=0;
  67.         if(t[x].ch[0]){t[t[x].ch[0]].val=t[x].val;t[t[x].ch[0]].sum=t[t[x].ch[0]].siz*t[x].val;t[t[x].ch[0]].lazy=1;}
  68.         if(t[x].ch[1]){t[t[x].ch[1]].val=t[x].val;t[t[x].ch[1]].sum=t[t[x].ch[1]].siz*t[x].val;t[t[x].ch[1]].lazy=1;}
  69.         if(t[x].val>=0)
  70.         {
  71.             if(t[x].ch[0]){t[t[x].ch[0]].lx=t[t[x].ch[0]].rx=t[t[x].ch[0]].mx=t[t[x].ch[0]].sum;}
  72.             if(t[x].ch[1]){t[t[x].ch[1]].lx=t[t[x].ch[1]].rx=t[t[x].ch[1]].mx=t[t[x].ch[1]].sum;}
  73.         }
  74.         else
  75.         {
  76.             if(t[x].ch[0]){t[t[x].ch[0]].lx=t[t[x].ch[0]].rx=0;t[t[x].ch[0]].mx=t[x].val;}
  77.             if(t[x].ch[1]){t[t[x].ch[1]].lx=t[t[x].ch[1]].rx=0;t[t[x].ch[1]].mx=t[x].val;}
  78.         }
  79.     }
  80.     if(t[x].mark)//mark表示已经交换了当前结点的左右儿子
  81.     {
  82.         t[x].mark=0;
  83.         if(t[x].ch[0])t[t[x].ch[0]].mark^=1;
  84.         if(t[x].ch[1])t[t[x].ch[1]].mark^=1;
  85.         swap(t[t[x].ch[0]].lx,t[t[x].ch[0]].rx);
  86.         swap(t[t[x].ch[1]].lx,t[t[x].ch[1]].rx);
  87.         //Attention:上面左儿子和右儿子的左右右子段交换，画图稍微模拟一下
  88.         swap(t[t[x].ch[0]].ch[0],t[t[x].ch[0]].ch[1]);
  89.         swap(t[t[x].ch[1]].ch[0],t[t[x].ch[1]].ch[1]);      
  90.     }
  91. }
  92. inline void Find(RG int x)
  93. //功能：把从root到x的路径一直pushdown
  94. {
  95.     top=0;zhan[++top]=x;
  96.     if(x==root){pushdown(x);return;}
  97.     while(t[x].fa!=root){zhan[++top]=t[x].fa;x=t[x].fa;}
  98.     zhan[++top]=root;
  99.     while(top){pushdown(zhan[top]);top--;}
  100. }
  101. inline void rotate(RG int x)
  102. //功能：把x旋转成x父亲的父亲
  103. {
  104.     RG int y=t[x].fa,z=t[y].fa;
  105.     RG int k=t[y].ch[1]==x;
  106.     t[z].ch[t[z].ch[1]==y]=x;  t[x].fa=z;
  107.     t[y].ch[k]=t[x].ch[k^1];   t[t[x].ch[k^1]].fa=y;
  108.     t[x].ch[k^1]=y;            t[y].fa=x;
  109.     pushup(y);
  110. }
  111. inline void splay(RG int x,RG int fa)
  112. //功能：把x旋转成为fa的儿子
  113. {
  114.     Find(x);
  115.     while(t[x].fa!=fa)
  116.     {
  117.         RG int y=t[x].fa,z=t[y].fa;
  118.         if(z!=fa)(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
  119.         rotate(x);
  120.     }
  121.     if(!fa)root=x;
  122.     pushup(x);
  123. }
  124. inline int Buildtree(RG int l,RG int r,RG int fa)
  125. //功能：a[l]到a[r]之间建立以fa为根的父亲的Splay并返回其根的结点编号
  126. {
  127.     if(l>r)return 0;
  128.     RG int x=Q.front();Q.pop();//从内存池中取出编号
  129.     if(l==r){t[x]=Get(a[l],fa,1);return x;}
  130.     RG int mid=(l+r)>>1;
  131.     t[x]=Get(a[mid],fa,1);
  132.     t[x].ch[0]=Buildtree(l,mid-1,x);
  133.     t[x].ch[1]=Buildtree(mid+1,r,x);
  134.     pushup(x);return x;
  135. }
  136. inline int Kth(RG int num)
  137. //功能：在Splay中找到第num个数并返回结点编号
  138. {
  139.     RG int x=root;
  140.     while(1)
  141.     {
  142.         pushdown(x);
  143.         RG int Size=t[t[x].ch[0]].siz;
  144.         if(num<=Size)x=t[x].ch[0];
  145.         if(num==Size+1)return x;
  146.         if(num>Size+1){num-=Size+1;x=t[x].ch[1];}
  147.     }
  148. }
  149. inline void Insert(RG int pos,RG int all)
  150. //功能：在第pos+1个数后插入all个数(哨兵影响)
  151. {
  152.     for(RG int i=1;i<=all;i++)a[i]=read();
  153.     RG int x=Kth(pos+1),next=Kth(pos+2);
  154.     splay(x,0);//pushdown(x);
  155.     splay(next,x);//pushdown(next);
  156.     t[next].ch[0]=Buildtree(1,all,next);
  157.     pushup(next);pushup(x);
  158. }
  159. inline void Recycle(RG int x)
  160. //功能：回收以x为根的子树中所有结点
  161. {
  162.     if(!x)return;
  163.     if(t[x].ch[0])Recycle(t[x].ch[0]);
  164.     if(t[x].ch[1])Recycle(t[x].ch[1]);
  165.     t[x]=Get(0,0,0);Q.push(x);
  166. }
  167. inline void Work(RG int pos,RG int all,RG int op)
  168. //功能：表示对区间[pos+1,pos+all]的操作(由于两个哨兵)
  169. //      op=1删除   op=2区间覆盖
  170. //      op=3翻转   op=4求和
  171. {
  172.     if(all==0){if(op==2)read();if(op==4)printf("0\n");return;}
  173.     //printf("[%d,%d]进行%d\n",pos+1,pos+all,op);
  174.     RG int last=Kth(pos),next=Kth(pos+all+1);
  175.     splay(last,0);//pushdown(last);
  176.     splay(next,last);//pushdown(next);
  177.     //这里不需要因为splay(x)的时候已经pushdown(x)了
  178.     RG int x=t[next].ch[0];
  179.     if(op==1)
  180.     {
  181.         Recycle(x);
  182.         t[next].ch[0]=0;
  183.     }
  184.     if(op==2)
  185.     {
  186.         c=read();t[x].lazy=1;
  187.         t[x].val=c;t[x].sum=t[x].siz*c;
  188.         if(c>=0){t[x].lx=t[x].rx=t[x].mx=t[x].sum;}
  189.         else{t[x].lx=t[x].rx=0;t[x].mx=c;}
  190.     }
  191.     if(op==3&&!t[x].lazy)
  192.     {
  193.         t[x].mark^=1;
  194.         swap(t[x].lx,t[x].rx);
  195.         swap(t[x].ch[0],t[x].ch[1]);
  196.     }
  197.     if(op==4)printf("%d\n",t[x].sum);
  198.     pushup(next);pushup(last);
  199. }
  200. int main()
  201. {
  202.     freopen("seq2005.in","r",stdin);
  203.     freopen("seq2005.out","w",stdout);
  204.     N=read();M=read();
  205.     t[0].mx=a[1]=a[N+2]=-1e9;
  206.     t[0].val=t[0].fa=t[0].siz=t[0].mark=t[0].lazy=0;
  207.     t[0].sum=t[0].ch[0]=t[0].ch[1]=t[0].lx=t[0].rx=0;   
  208.     for(RG int i=1;i<=MAXN-1;i++)Q.push(i);
  209.     for(RG int i=1;i<=N;i++)a[i+1]=read();//左右哨兵
  210.     root=Buildtree(1,N+2,0);
  211.     for(RG int i=1;i<=M;i++)
  212.     {
  213.         RG char s[20];scanf("%s",s);
  214.         //printf("%s\n",s);
  215.         if(s[0]!='M'||s[2]=='K'){pos=read();all=read();}
  216.         if(s[0]=='I')Insert(pos,all);//在pos后加入all个数
  217.         if(s[0]=='D')Work(pos,all,1);//在pos后删去all个数
  218.         if(s[0]=='M')
  219.         {
  220.             if(s[2]=='K')Work(pos,all,2);//区间覆盖
  221.             else printf("%d\n",t[root].mx);//最大子段和
  222.         }
  223.         if(s[0]=='R')Work(pos,all,3);//翻转
  224.         if(s[0]=='G')Work(pos,all,4);//求和
  225.         //Printtree();
  226.     }
  227.     return 0;
  228. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注