平衡树一直是自己的一大痛点……原因有两点：
1.原理有点绕，容易忘记
2.代码长，难码难调
不过遇到难点就退缩不是好的选择。于是在这里记录一下自己对于Splay的傻逼理解，以免自己忘记。
参考博客：http://blog.csdn.net/ric_shooter/article/details/20636487
首先要明确一点：平衡树（伸展树）的本质是二叉查找树——所以它查找节点位置和前驱（比自己小的最大的数）和后继（比自己大的最小的数）等等基本都是一样的，功能和二叉查找树基本一样。但二叉查找树的极限效率和暴力没有区别（链），所以要通过一种”旋转“操作来保证树的层数，从而保证复杂度为log--------至于为什么要这样旋转，别问我，网上也没有，问tarjian
那么关键就是理解旋转了。下面这张图很典型：
现在目标是对A和B进行旋转。
如果要把B旋转到父亲，对于B来说，它是A的左子树，所以右旋。首先，根据二叉搜索树的定义，A比B大，所以旋转后A是B的右儿子，D是B的左儿子不变。C同理不变。那么只剩E了：显然应该放在A的左儿子。对应到操作，应该如下：
1）把A的size减去D的size，因为它不再在A的子树中
2）把B的size加上E的size，因为它变到了A的子树里（注意处理A、B自己也要算在size里）
3）E的父亲设为A，A的父亲设为B，B的父亲设为A的父亲
是不是很简单？但打到代码里其实细节非常多，一定要细心，这也是为什么splay的常数巨大，代码长（常数小王子）
如果要把A旋转到父亲，对于A来说，它是B的右子树，所以左旋。其实会发现思路与代码和右旋一模一样，所以只要写一个rotate函数并且把”左和右“设置为”正方向和反方向即可“。具体实现看代码。
还有一个比较重要操作是splay，也就是判断是用zig还是zag还是zig-zig还是zig-zag还是zag-zig还是zag-zag。对于还未旋转到根的节点，两步合在一起能节省复杂度，原理问tarjian。根据所处位置判断即可。
每一次旋转都是要把一个节点旋转到根的。一定要记得什么时候要旋转，这样才正确！！！！
具体看代码，注释很 详 细。
（裸题bzoj 3224）
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 100010 #define RG register #define inf 0x3f3f3f3f #define Inf 99999999999999999LL using namespace std; typedef long long LL; int n,root,sum,opt,x,fa[N],siz[N],w[N],val[N],son[N][2]; inline int Abs(RG const int &a){return a>0?a:-a;} inline int Max(RG const int &a,RG const int &b){return a>b?a:b;} inline int Min(RG const int &a,RG const int &b){return a>b?b:a;} inline int gi(){ RG int x=0;RG bool flag=0;RG char c=getchar(); while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') c=getchar(),flag=1; while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return flag?-x:x; } inline void rotate(RG int x,RG int way){//旋转最关键，一定要记住它的原理啊啊啊啊啊！！！！ //牵涉到的东西有祖先、父亲、当前节点、当前节点兄弟，左儿子，右儿子 //way为正方向，1-way为反方向 int f=fa[x]; siz[f]+=siz[son[x][way]]-siz[x];//把父亲的siz减去当前节点及反方向儿子的siz(旋转后这部分不再在父亲管辖以内) siz[x]+=siz[f]-siz[son[x][way]];//把儿子的siz加上兄弟的siz，因为旋转以后他就变成当前节点的孙子了 son[f][1-way]=son[x][way]; //父亲反方向儿子就便成当前节点正方向儿子了 if(son[x][way]) fa[son[x][way]]=f; fa[x]=fa[f]; if(fa[f]){ if(f==son[fa[f]][0]) son[fa[f]][0]=x; else son[fa[f]][1]=x; } fa[f]=x; son[x][way]=f; } inline void splay(RG int x){ while(fa[x]){ RG int f=fa[x]; if(!fa[f]){ if(x==son[f][0]) rotate(x,1); else rotate(x,0);//若当前节点为根节点的儿子，则直接旋转(zig or zag) } else{//至少有两层，直接zig-zig or zag-zag or zig-zag or zag-zig if(f==son[fa[f]][0]){//重要！！！！在左边就右旋，在右边就左旋(与当前方向相反) if(x==son[f][0]){ rotate(f,1); rotate(x,1);//玄学的力量：zig-zig,zag-zag先旋转father在旋转自己效率更高 } else{ rotate(x,0); rotate(x,1);//但zig-zag和zag-zig必须从自己开始！ } } else{ if(x==son[f][0]){ rotate(x,1); rotate(x,0); } else{ rotate(f,0); rotate(x,0); } } } } root=x; } inline int findloc(RG int x,RG int goal){ while(w[x]!=goal){ if(goal<w[x]){ if(!son[x][0]) break; x=son[x][0]; } else{ if(!son[x][1]) break; x=son[x][1]; } } return x; } inline void ins(RG int x){ if(!sum){ sum=1;w[1]=x; root=1;fa[1]=0; siz[1]=1;val[1]=1; return; } RG bool flag=0; RG int nowloc=findloc(root,x),hold; if(w[nowloc]==x){ flag=1; hold=nowloc; ++val[nowloc]; } else{ ++sum; siz[sum]=1;val[sum]=1; w[sum]=x;fa[sum]=nowloc; if(w[nowloc]>x) son[nowloc][0]=sum; else son[nowloc][1]=sum; } while(nowloc){ ++siz[nowloc]; nowloc=fa[nowloc]; } if(flag) splay(hold); else splay(sum); }//插入操作与普通的二叉搜索树完全一样，只是最后指向splay旋转 inline int bignum(RG int x,RG int way){ const int hehe[2]={inf,-inf}; RG int nowloc=findloc(x,hehe[way]);//找到对应路径的权值最大(小)节点 大对应左子树 小对应右子树 RG int ww=w[nowloc]; splay(nowloc);//将这个点转到最顶端 return ww; } inline void del(RG int x){ int nowloc=findloc(root,x),f; splay(nowloc);//已经splay，当前节点在树顶 if(w[nowloc]!=x) return; --val[nowloc]; --siz[nowloc]; if(val[nowloc]) return;//节点不止一个，直接删除即可； else{ w[nowloc]=0; if(!son[nowloc][0]){ f=son[nowloc][1]; son[nowloc][1]=0; root=f; fa[root]=0;//没有左子树，又子树即为根 } else{ fa[son[nowloc][0]]=0;//切断左子树与根节点的关联（此时左边完全独立出来） f=bignum(son[nowloc][0],0);//左子树构成了一颗全新splay son[root][1]=son[nowloc][1];//其右儿子即为当前节点右儿子——左右子树合并 siz[root]+=siz[son[nowloc][1]]; if(son[root][1]) fa[son[root][1]]=root; son[nowloc][0]=son[nowloc][1]=0; } } } inline int numrank(RG int x){ int nowloc=findloc(root,x); splay(nowloc); root=nowloc; return siz[son[nowloc][0]]+1; } inline int ranknum(RG int x,RG int way){ int now=root,hold; while(!((x>=siz[son[now][way]]+1)&&(x<=siz[son[now][way]]+val[now])&&now)){//如果不满足条件 if(x>siz[son[now][way]]+val[now]){//如果左边还要大于所求区间，往右边找 x-=siz[son[now][way]]+val[now]; now=son[now][1-way]; } else now=son[now][way];//x过小，往左找 } hold=now; splay(now); return hold; } inline int pre(RG int x){ RG int nowloc=findloc(root,x); splay(nowloc); if(w[nowloc]<x) return w[nowloc]; return bignum(son[nowloc][0],0); } inline int back(RG int x){ RG int nowloc=findloc(root,x); splay(nowloc); if(w[nowloc]>x) return w[nowloc]; return bignum(son[nowloc][1],1); }//类似普通二叉搜索树查找，只不过记得翻转保证复杂度 inline void work(){ n=gi(); for (RG int i=1;i<=n;++i){ opt=gi();x=gi(); switch(opt){ case 1 : ins(x);break; case 2 : del(x);break; case 3 : printf("%d ",numrank(x));break; case 4 : printf("%d ",w[ranknum(x,0)]);break; case 5 : printf("%d ",pre(x));break; case 6 : printf("%d ",back(x));break; default : break; } } } int main(){ freopen("3224.in","r",stdin); freopen("3224.out","w",stdout); work(); fclose(stdin); fclose(stdout); return 0; }
数据结构这种东西从来都是难写难调的。一定要细心。学会造数据调试。勤加练习。