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

伸展树(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. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注