一直觉得平衡树水很深，有机会想好好搞一搞，这里记下我大致总结的内容吧。
平衡树主要有以下几种类型：
1.严格保证深度：红黑树、AVL等。这类平衡树始终把深度维护在logn级别，并且每次也只用logn的时间维护自己的性质，因为每次操作都是严格logn，常数会比较小，但伴随的一般是树的形态限制较死，编写时需要考虑的情况可能较多，代码难度较大等。
2.均摊复杂度：Splay、替罪羊等。每次操作可能O(1)可能O(n)，但这并不妨碍它们最终复杂度只有O(nlogn)，依据一般是复杂的势能分析之类，不深入研究的话只要记住它们效率可以保证就行了。此类平衡树无法可持久化，强行可持久化会导致无法均摊，复杂度退化。（替罪羊可以部分可持久化（不修改历史版本））
3.玄学即正解：Treap、跳表（假装是平衡树）等。用上一些随机策略，最后每次期望O(logn)，随机的思想不仅几乎卡不掉，而且不像其他类平衡树为保持平衡加上了很多限制，这也使得没有太多限制的随机化平衡树充满待挖掘的潜力。
4.根本不平衡：普通BST、Spaly等。快利用Trajan大神发明的Spaly算法O(1)维护平衡树。
下面分别介绍这些平衡树（加粗的是在目前信息学竞赛中较为重要的）
介绍的时候顺便贴下模板，因为如果都是字有点吓人……
模板题->n个操作，支持插入一个数和查找k大(n<=500,000)。数据大部分随机，小部分特殊构造。给出大致的运行时间，仅供参考。
[基于模板题的效率对比] （可能由于我写的丑/问题特殊性/随机数据/随机种子生成器/评测机状态等原因产生一定误差，仅供参考）（还有缺的以后有机会再补）
替罪羊树(504ms) < AVL树(588ms) < 普通Treap(688ms) < 无旋Treap(1000ms) < 双旋Splay(1220ms) < 混合旋Splay(1384ms) < 随机合并树(TLE) < 单旋Spaly(TLE) < 裸BST(TLE)
可以看到替罪羊树的效率十分出色（可能是因为主要是随机数据），AVL和Treap紧随其后，无旋Treap和Splay功能强大但常数较大，后面纯属娱乐。
这里先贴个本题目前的Rank1 写的是权值线段树ZKW版 240ms 感觉已经接近极限了，还可以调整的就是可以把排序换成O(n)的
#include<cstdio> #include<algorithm> using namespace std; #define r register int char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 500000 #define N 524288 int x[MN+5],y[MN+5],t[N*2+5],c[MN+5],rk[MN+5]; bool cmp(int a,int b){return y[a]<y[b];} void add(r k){for(k+=N;k;k>>=1)++t[k];} int find(r k){for(r i=1;i<<=1;){if(t[i]<k)k-=t[i++];if(i>N)return i-N;}} int main() { fread(B,1,1<<26,stdin); r n=read(),i; for(i=1;i<=n;++i)x[i]=read(),y[i]=read(),c[i]=i; sort(c+1,c+n+1,cmp); for(i=1;i<=n;++i)rk[c[i]]=i; for(i=1;i<=n;++i)x[i]?(add(rk[i]),0):printf("%d ",y[c[find(y[i])]]); }
正文
红黑树：好像性质比较复杂，我也不是很懂，据说效率是目前各类平衡树中最高的，代码也是最难写的。我还不是很懂，有机会再补。
AVL树：我最开始学的就是AVL，因为很好理解，听说这玩意儿代码很长，但我一点都不觉得（我可能学的假的）。性质是任意节点左右子树深度差不超过1，不满足就旋一旋，要考虑各种情况保证旋完满足性质，用一些代码小技巧写起来还是挺短的。后来发现这种平衡树只能做最基本的操作，赶紧跳坑Splay。
#include<cstdio> #include<algorithm> using namespace std; char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 500000 #define rtf MN+1 #define L(x) c[x][0] #define R(x) c[x][1] #define rt L(rtf) int fa[MN+5],c[MN+5][2],s[MN+5],h[MN+5],z[MN+5],tn; inline void update(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;h[x]=max(h[c[x][0]],h[c[x][1]])+1;} void rotate(int x) { int f=fa[x],ff=fa[f],l=R(f)==x,r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][R(ff)==f]=x;c[f][l]=c[x][r];c[x][r]=f; update(f);update(x); } void ins(int f,int t,int x) { if(!c[f][t]){fa[c[f][t]=++tn]=f;s[tn]=1;z[tn]=x;return;} f=c[f][t];ins(f,x>z[f],x); if(h[L(f)]-h[R(f)]>2){if(h[R(L(f))]>h[L(L(f))])rotate(R(L(f)));rotate(L(f));} else if(h[R(f)]-h[L(f)]>2){if(h[L(R(f))]>h[R(R(f))])rotate(L(R(f)));rotate(R(f));} update(f); } int find(int x,int k) { if(k<=s[L(x)])return find(L(x),k); if(k-=s[L(x)]+1)return find(R(x),k); return z[x]; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t)ins(rtf,0,x); else printf("%d ",find(rt,x)); } }
伸展树（Splay Tree）：全国人民都在用。你啥平衡树都可以不会，但你不能不会Splay。OI中经常要弄一些区间翻转区间查询之类的，提取区间最方便最广为人知的应该就是Splay了吧。Splay基本思想就是每次访问树中节点都要把节点双旋旋到根上来（旋法百度都有比较详细的说明，这里不再赘述），即使一开始树不平衡，旋到根上树的结构就慢慢平衡了。一系列复杂度分析可以保证它是均摊nlogn的（单旋就没有任何保证），但是还是改变不了它常数巨大的缺点。其实有个隐藏的性质就是越高频访问同一些节点，Splay的效率就会越高（因为靠近根），这个性质在现实中可能有一些应用，但OI中难以用题目的形式表现出来（甚至还有人专门卡你）……Splay还是Link-Cut Tree的重要组件。Splay提取区间的方法是把左右端点旋到根附近，例如[l,r]就把l-1旋到根，r+1旋到根节点的右儿子，那么根节点右儿子的左儿子就是[l,r]区间，一般要建两个辅助点0和n+1来提取[1,n]。
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 500000 #define rt MN+1 int fa[MN+5],c[MN+5][2],s[MN+5],v[MN+5],tn; inline void update(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;} void rotate(int x) { int f=fa[x],ff=fa[f],l,r; l=c[f][1]==x;r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][c[ff][1]==f]=x;c[f][l]=c[x][r];c[x][r]=f; update(f); } void splay(int x,int r) { for(int f;fa[x]!=r;rotate(x)) if(fa[f=fa[x]]!=r)rotate(c[fa[f]][0]==f^c[f][1]==x?f:x); update(x); } void ins(int f,int t,int z) { if(!c[f][t]){fa[c[f][t]=++tn]=f;v[tn]=z;splay(tn,rt);return;} ++s[f=c[f][t]]; ins(f,z>v[f],z); } int find(int x,int k) { if(k<=s[c[x][0]])return find(c[x][0],k); if(k-=s[c[x][0]]+1)return find(c[x][1],k); splay(x,rt);return x; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t)ins(rt,0,x); else printf("%d ",v[find(c[rt][0],x)]); } }
自己瞎写的混合旋Splay
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 500000 #define rt MN+1 int fa[MN+5],c[MN+5][2],s[MN+5],v[MN+5],tn; inline void update(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;} void rotate(int x) { int f=fa[x],ff=fa[f],l,r; l=c[f][1]==x;r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][c[ff][1]==f]=x;c[f][l]=c[x][r];c[x][r]=f; update(f); } void splay(int x,int r) { for(int f;fa[x]!=r;rotate(x)) if(fa[f=fa[x]]!=r&&c[fa[f]][0]==f^c[f][1]==x)rotate(f); update(x); } void ins(int f,int t,int z) { if(!c[f][t]){fa[c[f][t]=++tn]=f;v[tn]=z;splay(tn,rt);return;} ++s[f=c[f][t]]; ins(f,z>v[f],z); } int find(int x,int k) { if(k<=s[c[x][0]])return find(c[x][0],k); if(k-=s[c[x][0]]+1)return find(c[x][1],k); splay(x,rt);return x; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t)ins(rt,0,x); else printf("%d ",v[find(c[rt][0],x)]); } }
单旋Spaly
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 500000 #define rt MN+1 int fa[MN+5],c[MN+5][2],s[MN+5],v[MN+5],tn; inline void update(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;} void rotate(int x) { int f=fa[x],ff=fa[f],l,r; l=c[f][1]==x;r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][c[ff][1]==f]=x;c[f][l]=c[x][r];c[x][r]=f; update(f); } void splay(int x,int r) { while(fa[x]!=r)rotate(x); update(x); } void ins(int f,int t,int z) { if(!c[f][t]){fa[c[f][t]=++tn]=f;v[tn]=z;splay(tn,rt);return;} ++s[f=c[f][t]]; ins(f,z>v[f],z); } int find(int x,int k) { if(k<=s[c[x][0]])return find(c[x][0],k); if(k-=s[c[x][0]]+1)return find(c[x][1],k); splay(x,rt);return x; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t)ins(rt,0,x); else printf("%d ",v[find(c[rt][0],x)]); } }
替罪羊树（Scapegoat Tree）：先取一个α值(大约0.6~0.8之间)，平衡的条件为每个节点的左右子树大小都不超过整棵子树的α倍，每次插入向上找到最高的不满足平衡条件的节点（称为“替罪羊节点”），暴力重构整棵子树（按顺序提取出整棵子树节点、取中间作为根，前一半作为左子树、后一半作为右子树，递归处理），删除节点的时候打个标记表示该节点已被删除，维护信息时不统计该节点，重构的时候彻底删掉即可。可以证明替罪羊树的时间复杂度均摊O(nlogn)。α取的小重构次数就会增多，取的大每次操作的平均深度就会变大，看情况权衡一下，不会权衡就看心情取吧，反正都是nlogn。替罪羊树的一个重要应用就是套其他树，因为替罪羊树不需要旋转（旋转的时候没法一并维护套着的树），每次重构的时候也可以把套着的树一并重构。
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 500000 #define rt MN+1 int c[MN+5][2],fa[MN+5],s[MN+5],z[MN+5],tn,lw,a[MN+5],cnt; void ins(int f,int t,int x) { if(!c[f][t]){fa[c[f][t]=++tn]=f;s[tn]=1;z[tn]=x;return;} ++s[f=c[f][t]]; ins(f,x>z[f],x); if(s[c[f][0]]>s[f]*0.75||s[c[f][1]]>s[f]*0.75)lw=f; } int find(int x,int k) { if(k<=s[c[x][0]])return find(c[x][0],k); if(k-=s[c[x][0]]+1)return find(c[x][1],k); return z[x]; } void get(int x) { if(!x)return; get(c[x][0]); a[++cnt]=x; get(c[x][1]); } void build(int f,int t,int l,int r) { if(l>r)return; int mid=l+r>>1; fa[c[f][t]=a[mid]]=f;s[f=c[f][t]]=r-l+1; c[f][0]=c[f][1]=0; build(f,0,l,mid-1);build(f,1,mid+1,r); } void rebuild(int x) { cnt=0;get(x); build(fa[x],c[fa[x]][1]==x,1,cnt); } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t){ins(rt,0,x);if(lw)rebuild(lw),lw=0;} else printf("%d ",find(c[rt][0],x)); } }
树堆（Treap）：Treap分为两种，普通的Treap和无旋Treap。
普通Treap：给每个节点分配一个随机权值，在本身键值满足二叉搜索树性质时，要求各节点权值满足堆的性质，实现很简单，插入一个点时，随机分配一个权值，若它父亲权值比他大/小（看你写的是大根堆还是小根堆），就把它旋上去，直到旋到根为止，删除可以每次选择左右儿子中权值较大/小的旋上来，直到把要删的这个点旋成叶子后直接删掉，还有一种删除方法是直接重构整棵子树，看上去很暴力实际上是有复杂度保证的，可参见CLJ重量平衡树的论文。Treap所有操作的复杂度期望均为每次O(logn)，自己脑补的一种证明如下：设一棵n个点小根Treap随机权值范围为0~x，则一个节点的权值期望为x/2，而它的父节点权值小于它，则父节点的权值期望为x/4，平均有n/2个节点可能满足，他父节点的父节点权值小于父节点，权值期望x/8，平均有n/4个节点可能满足……儿子同理。如此推导容易得出，Treap的深度期望是O(logn)的，那么每次操作的复杂度期望也为O(logn)。这种Treap作为一个效率高，易于实现的平衡树在OI中比较常用。顺带一提，Treap也是重量平衡树，也就是说，你在上面套树，旋转时暴力重构，总复杂度仍为O(nlogn)，感觉很神奇（随机的力量！）。
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } inline int ran() { static int x=23333; return x^=x<<13,x^=x>>17,x^=x<<5; } #define MN 500000 #define rtf MN+1 #define rt c[rtf][0] int fa[MN+5],c[MN+5][2],s[MN+5],z[MN+5],p[MN+5],tn; inline void update(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;} void rotate(int x) { int f=fa[x],ff=fa[f],l,r; l=c[f][1]==x;r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][c[ff][1]==f]=x;c[f][l]=c[x][r];c[x][r]=f; update(f);update(x); } void ins(int f,int t,int x) { if(!c[f][t]) { fa[c[f][t]=++tn]=f; z[tn]=x;p[tn]=ran();s[tn]=1; while(fa[tn]!=rtf&&p[fa[tn]]<p[tn])rotate(tn); return; } ++s[f=c[f][t]];ins(f,x>z[f],x); } int find(int x,int k) { if(k<=s[c[x][0]])return find(c[x][0],k); if(k-=s[c[x][0]]+1)return find(c[x][1],k); return x; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t)ins(rtf,0,x); else printf("%d ",z[find(rt,x)]); } }
无旋Treap：普通的Treap虽然不错，但比起接下来要介绍的无旋Treap来说可谓小巫见大巫。无旋Treap的核心是两个操作：merge和split，分别是合并两棵Treap和把一棵Treap拆成两半。merge操作每次选根节点权值大的Treap，然后以这棵的根节点作为合并后的根节点，保留一颗子树，把另一棵子树和另一棵Treap合并；split操作一般是把前k个拆成一棵，剩下的拆成另一棵，先找到第k大在哪棵子树，然后把这棵子树劈开，类似地递归处理就好了。插入操作只要按插入的位置把树劈开，然后把两棵树和一个新的节点合并。无旋Treap比起普通Treap更厉害的地方在于它可以提取区间：你只要把树劈成好几段就可以了。这里可以撤回上面说的不能不学Splay，你学了无旋Treap之后，几乎可以完全替代Splay啦（Link-Cut Tree可能还要考虑一下……），不仅常数小于Splay，What's more，你还可以把它可持久化！但是也有一个问题，如果要区间复制的话，就会无法保持权值的堆性质，复杂度就会变得无法保证……解决方案有几个，一个是不管堆性质了，合并时碰到相同就随机选，还有就是把复制的赋新的权值，不过都很玄学（目前个人发现效率最高的方法是合并时碰到相同随机一个权值++）。其实无旋Treap可以直接不记权值，合并时随机选一个作为根，不过这样不知道复杂度怎样了，刷脸A题，而且这样连堆都不是了，干脆叫Random Tree？（纯属口胡）
#include<cstdio> #include<algorithm> using namespace std; char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } inline int ran() { static int x=23333; return x^=x<<13,x^=x>>17,x^=x<<5; } struct node { node*l,*r;int s,z,p; node(int x){l=r=0;s=1;z=x;p=ran();} }*rt; struct np{node*a,*b;}; inline int sz(node*a){return a?a->s:0;} inline node*up(node*a){return a->s=sz(a->l)+sz(a->r)+1,a;} node*merge(node*a,node*b) { if(!a)return b;if(!b)return a; if(a->p>b->p)return a->r=merge(a->r,b),up(a); return b->l=merge(a,b->l),up(b); } np split(node*a,int k) { if(!a)return(np){0,0}; np p=split(a->z>k?a->l:a->r,k); return a->z>k?(np){p.a,(a->l=p.b,up(a))}:(np){(a->r=p.a,up(a)),p.b}; } int find(node*a,int k) { if(k<=sz(a->l))return find(a->l,k); if(k-=sz(a->l)+1)return find(a->r,k); return a->z; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t){np p=split(rt,x);rt=merge(merge(p.a,new node(x)),p.b);} else printf("%d ",find(rt,x)); } }
上面提到的随机合并树
#include<cstdio> #include<algorithm> using namespace std; char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } inline int ran() { static int x=23333; return x^=x<<13,x^=x>>17,x^=x<<5; } struct node { node*l,*r;int s,z; node(int x){l=r=0;s=1;z=x;} }*rt; struct np{node*a,*b;}; inline int sz(node*a){return a?a->s:0;} inline node*up(node*a){return a->s=sz(a->l)+sz(a->r)+1,a;} node*merge(node*a,node*b) { if(!a)return b;if(!b)return a; if(ran()&1)return a->r=merge(a->r,b),up(a); return b->l=merge(a,b->l),up(b); } np split(node*a,int k) { if(!a)return(np){0,0}; np p=split(a->z>k?a->l:a->r,k); return a->z>k?(np){p.a,(a->l=p.b,up(a))}:(np){(a->r=p.a,up(a)),p.b}; } int find(node*a,int k) { if(k<=sz(a->l))return find(a->l,k); if(k-=sz(a->l)+1)return find(a->r,k); return a->z; } int main() { fread(B,1,1<<26,stdin); int n=read(),t,x; while(n--) { t=read();x=read(); if(t){np p=split(rt,x);rt=merge(merge(p.a,new node(x)),p.b);} else printf("%d ",find(rt,x)); } }
跳表（Skip List）：不是平衡树，却能做平衡树的操作，复杂度和常数也不错，非常有意思。时间复杂度期望O(nlogn)，空间期望O(2n)，是不是觉得和线段树有点像？没错，其实它最后的结构也类似线段树，但却能支持插入！从链表开始说起，普通链表需要O(n)来完成查找，但找到位置后只要O(1)插入，于是就有人用了分块思想，假设总共N个元素，我们建一个大链表，大链表里存K个小链表，每个小链表里存至多N/K个元素，插入时如果小链表内元素过多，就拆成两个小链表，每次操作复杂度为O（K+N/K），K约为N^0.5时有最小复杂度O(N^0.5)。不由得联想到区间求和的分块思想：每N^0.5个数预处理求和，每次查询复杂度也为O(N^0.5)。区间求和是如何用线段树做到O(logn)的呢？就是分层，每一层两个信息合并成一个，于是我们的链表也能使用类似的思想。每次插入，我们随机为这个点分配层数，一开始为一层，每次投硬币（当然是假的啦），1/2的概率多加一层，1/2的概率停止。这样我们底层的N个元素平均有N/2的进入第二层，N/4进入第三层……最后出现的结构几乎和线段树一模一样！（假设你运气足够好）同理在这些点上维护区间信息，复杂度也有期望上的保证。唯一的缺憾就是和线段树一样，它并不能提取区间。跳表这个数据结构结合了链表和线段树的思想，并利用随机化原理，将二者合为一体，虽然目前它的功能还不够强大，不过这种思路应该是很有启发性的。
跳表模板暂缺