从BST引入。
我们要高效查找一个值，那么在保证左儿子小于右儿子的二叉树上跳，期望\(O(d)\)，\(d\)为深度。
二叉搜索树BST
最好\(O(\log n)\)，最坏\(O(n)\)。
左子树的权值小于根的权值小于右子树的权值。
P用没有。
替罪羊树
是一种依靠重构来维持平衡的重量平衡树。在插入删除时发现沿途失衡，就将当前子树暴力重构。
通过设置比例常数\(\alpha\in(0.5,1)\)来判断是否能重构。若当前节点的子节点的大小占它的大小的比例超过了\(\alpha\)。
另外由于采用惰性删除，只是计数器减一，以删除节点过多也会影响效率，所以当未被删除的节点个数占总大小的比例低于\(\alpha\)时，也要重构。
时间复杂度\(O(n\log n)\)。这种树的重构方式比起根号重构更优秀，在其他东西（比如带修的点分树）中也可以借鉴。
板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1e5+1;
const double alpha=0.8;
int lc[maxn],rc[maxn],val[maxn],w[maxn],s[maxn],siz[maxn],sd[maxn],ldr[maxn],sz,rt,n,m,last=0,ans=0,op,p,rnk,num,pre,sub;
inline void pushup(int k){
s[k]=s[lc[k]]+s[rc[k]]+1;
siz[k]=siz[lc[k]]+siz[rc[k]]+w[k];
sd[k]=sd[lc[k]]+sd[rc[k]]+(w[k]!=0);
}
inline bool canreb(int k){
return w[k]&&((double)max(s[lc[k]],s[rc[k]])>=alpha*s[k]||(double)sd[k]<=alpha*s[k]);
}
void rebfla(int &ldc,int k){
if(!k) return;
rebfla(ldc,lc[k]);
if(w[k]) ldr[ldc++]=k;
rebfla(ldc,rc[k]);
}
int rebuild(int l,int r){
if(l>=r) return 0;
int mid=(l+r)>>1;
lc[ldr[mid]]=rebuild(l,mid);
rc[ldr[mid]]=rebuild(mid+1,r);
pushup(ldr[mid]);
return ldr[mid];
}
void reb(int &k){
int ldc=0;
rebfla(ldc,k);
k=rebuild(0,ldc);
}
void insert(int &k,int x){
if(!k){
k=++sz;
if(!rt) rt=1;
val[k]=x;
lc[k]=rc[k]=0;
w[k]=s[k]=siz[k]=sd[k]=1;
return;
}
else{
if(val[k]==x) w[k]++;
else if(val[k]<x) insert(rc[k],x);
else insert(lc[k],x);
pushup(k);
if(canreb(k)) reb(k);
}
}
void del(int &k,int x){
if(!k) return;
else {
if(val[k]==x){
if(w[k]) w[k]--;
}
else{
if(val[k]<x) del(rc[k],x);
else del(lc[k],x);
}
pushup(k);
if(canreb(k)) reb(k);
}
}
int upper(int k,int x){
if(!k) return 1;
else if(val[k]==x&&w[k]) return siz[lc[k]]+w[k]+1;
else if(val[k]<x) return siz[lc[k]]+w[k]+upper(rc[k],x);
else return upper(lc[k],x);
}
int unupper(int k,int x){
if(!k) return 0;
else if(val[k]==x&&w[k]) return siz[lc[k]];
else if(val[k]<x) return siz[lc[k]]+w[k]+unupper(rc[k],x);
else return unupper(lc[k],x);
}
int querynum(int k,int x){
if(!k) return 0;
else if(siz[lc[k]]>=x) return querynum(lc[k],x);
else if(siz[lc[k]]+w[k]<x) return querynum(rc[k],x-siz[lc[k]]-w[k]);
else return val[k];
}
int querypre(int k,int x){
return querynum(k,unupper(k,x));
}
int querysub(int k,int x){
return querynum(k,upper(k,x));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&p);
insert(rt,p);
}
while(m--){
scanf("%d%d",&op,&p);
p=p^last;
if(op==1) insert(rt,p);
else if(op==2) del(rt,p);
else if(op==3){
rnk=unupper(rt,p)+1;
last=rnk;
ans^=rnk;
}
else if(op==4){
num=querynum(rt,p);
last=num;
ans^=num;
}
else if(op==5){
pre=querypre(rt,p);
last=pre;
ans^=pre;
}
else if(op==6){
sub=querysub(rt,p);
last=sub;
ans^=sub;
}
}
printf("%d\n",ans);
return 0;
}
Treap
是一种弱平衡的二叉搜索树。同时符合堆和二叉搜索树的性质。
堆的权值为随机权值，以保证复杂度。
当堆的性质被破坏需要调整时，有旋Treap通过左旋或右旋来调整。FHQ-Treap在合并时使用随机赋的权值。
小根堆或者大根堆都行，都是为了复杂度正确。
注意到随机权值可以保证树高为\(\log n\)的，于是可以大胆做一些看似暴力实则正确的操作。
有旋Treap
板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=100004;
int l[maxn],r[maxn],val[maxn],siz[maxn],rnd[maxn],w[maxn],sz,ans,rt,n,op,a;
inline void pushup(int k)
{
siz[k]=siz[l[k]]+siz[r[k]]+w[k];
}
inline void rrotate(int &k)
{
int t=l[k];
l[k]=r[t];
r[t]=k;
siz[t]=siz[k];
pushup(k);
k=t;
}
inline void lrotate(int &k)
{
int t=r[k];
r[k]=l[t];
l[t]=k;
siz[t]=siz[k];
pushup(k);
k=t;
}
void insert(int &k,int x)
{
if(!k)
{
++sz;
k=sz;
val[k]=x;
siz[k]=1;
w[k]=1;
rnd[k]=rand();
return;
}
siz[k]++;
if(val[k]==x)
{
w[k]++;
}
else if(val[k]<x)
{
insert(r[k],x);
if(rnd[r[k]]<rnd[k]) lrotate(k);
}
else
{
insert(l[k],x);
if(rnd[l[k]]<rnd[k]) rrotate(k);
}
}
bool del(int &k,int x)
{
if(!k) return false;
if(val[k]==x)
{
if(w[k]>1)
{
w[k]--;
siz[k]--;
return true;
}
if(l[k]==0||r[k]==0)
{
k=l[k]+r[k];
return true;
}
else if(rnd[l[k]]<rnd[r[k]])
{
rrotate(k);
return del(k,x);
}
else
{
lrotate(k);
return del(k,x);
}
}
else if(val[k]<x)
{
bool suc=del(r[k],x);
if(suc) siz[k]--;
return suc;
}
else
{
bool suc=del(l[k],x);
if(suc) siz[k]--;
return suc;
}
}
int queryrank(int k,int x)
{
if(!k) return 0;
if(x==val[k])
{
return siz[l[k]]+1;
}
else if(x>val[k])
{
return siz[l[k]]+w[k]+queryrank(r[k],x);
}
else
{
return queryrank(l[k],x);
}
}
int querynum(int k,int x)
{
if(!k) return 0;
else if(x<=siz[l[k]])
{
return querynum(l[k],x);
}
else if(x>siz[l[k]]+w[k])
{
return querynum(r[k],x-siz[l[k]]-w[k]);
}
else
{
return val[k];
}
}
void querypre(int k,int x)
{
if(!k) return;
else if(val[k]<x)
{
ans=k;
querypre(r[k],x);
}
else querypre(l[k],x);
}
void querysub(int k,int x)
{
if(!k) return;
else if(val[k]>x)
{
ans=k;
querysub(l[k],x);
}
else querysub(r[k],x);
}
int main()
{
srand(1919810);
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&op,&a);
if(op==1)
{
insert(rt,a);
}
else if(op==2)
{
del(rt,a);
}
else if(op==3)
{
printf("%d\n",queryrank(rt,a));
}
else if(op==4)
{
printf("%d\n",querynum(rt,a));
}
else if(op==5)
{
ans=0;
querypre(rt,a);
printf("%d\n",val[ans]);
}
else if(op==6)
{
ans=0;
querysub(rt,a);
printf("%d\n",val[ans]);
}
}
return 0;
}
无旋Treap（FHQ-Treap）
最重要的操作是分裂与合并。分裂通过引用\(l,r\)返回分裂出的两棵树的根，分为按值分裂（\(val\le x\)的在\(l\)，其余在\(r\)），和按排名分裂（\(rk\le k\)的在\(l\)，其余在\(r\)）。合并通过引用返回合并后的根。
板子
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
int rd(){
int f=1,r=0;
char ch=gc();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=gc();}
while(isdigit(ch)){ r=(r<<3)+(r<<1)+(ch^48);ch=gc();}
return f*r;
}
mt19937 rnd(19260817);
const int maxn=1e5+10;
int n,tot,rt,sz[maxn],rv[maxn],val[maxn],ch[2][maxn];
#define ls(k) (ch[0][k])
#define rs(k) (ch[1][k])
void pushup(int u){
sz[u]=sz[ls(u)]+sz[rs(u)]+1;
}
int newnode(int v){
sz[++tot]=1;
rv[tot]=rnd();
val[tot]=v;
return tot;
}
void splitv(int u,int v,int &l,int &r){
if(!u){
l=r=0;
return;
}
if(val[u]<=v) l=u,splitv(rs(u),v,rs(l),r);
else r=u,splitv(ls(u),v,l,ls(r));
pushup(u);
}
void splitsz(int u,int k,int &l,int &r){
if(!u){
l=r=0;
return;
}
if(sz[ls(u)]+1<=k) l=u,splitsz(rs(u),k-sz[ls(u)]-1,rs(l),r);
else r=u,splitsz(ls(u),k,l,ls(r));
pushup(u);
}
void merge(int &u,int l,int r){
if(!l||!r){
u=l+r;
if(u) pushup(u);
return;
}
if(rv[l]>rv[r]) u=l,merge(rs(u),rs(l),r);
else u=r,merge(ls(u),l,ls(r));
pushup(u);
}
void insert(int x){
int rtl=0;
splitv(rt,x,rtl,rt);
merge(rtl,rtl,newnode(x));
merge(rt,rtl,rt);
}
void del(int x){
int rt1=0;
splitv(rt,x,rt1,rt);
int rt2=0;
splitv(rt1,x-1,rt2,rt1);
int rt3=0;
splitsz(rt1,1,rt3,rt1);
merge(rt1,rt2,rt1);
merge(rt,rt1,rt);
}
int qryrk(int x){
int rt1=0;
splitv(rt,x-1,rt1,rt);
int rs=sz[rt1]+1;
merge(rt,rt1,rt);
return rs;
}
int qryval(int x){
int rt1=0;
splitsz(rt,x,rt1,rt);
int rt2=0;
splitsz(rt1,x-1,rt2,rt1);
int rs=val[rt1];
merge(rt1,rt2,rt1);
merge(rt,rt1,rt);
return rs;
}
int qrymx(int u){
if(rs(u)) return qrymx(rs(u));
return val[u];
}
int qrymi(int u){
if(ls(u)) return qrymi(ls(u));
return val[u];
}
int qrypre(int x){
int rt1=0;
splitv(rt,x-1,rt1,rt);
int rs=qrymx(rt1);
merge(rt,rt1,rt);
return rs;
}
int qrysuf(int x){
int rt1=0;
splitv(rt,x,rt1,rt);
int rs=qrymi(rt);
merge(rt,rt1,rt);
return rs;
}
void solve(){
int op=rd(),x=rd();
if(op==1) insert(x);
else if(op==2) del(x);
else if(op==3) printf("%d\n",qryrk(x));
else if(op==4) printf("%d\n",qryval(x));
else if(op==5) printf("%d\n",qrypre(x));
else printf("%d\n",qrysuf(x));
return;
}
int main(){
n=rd();
while(n--) solve();
return 0;
}
FHQ-Treap更好写，可以持久化，结构更加灵活，这是相较于有旋Treap的优势。
Splay
时间复杂度靠均摊保证，每次操作后需要Splay()操作来保证时间复杂度，于是不太稳定，但很重要。可以说Splay的结构是平衡树中最灵活的，除了不能分裂合并。
板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,sz=0,rt,a[maxn];
struct TREE{
int val,siz,fa,ch[2],tag;
inline void init(int _v,int _fa,int _siz,int _tag){
val=_v,fa=_fa,siz=_siz,tag=_tag;
}
}t[maxn];
inline void pushup(int k){
t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+1;
}
inline void pushdown(int k){
if(t[k].tag){
swap(t[k].ch[0],t[k].ch[1]);
t[t[k].ch[0]].tag^=1;
t[t[k].ch[1]].tag^=1;
t[k].tag=0;
}
}
int build(int f,int l,int r){
if(l>r) return 0;
int mid=(l+r)>>1;
int k=++sz;
t[k].init(a[mid],f,1,0);
t[k].ch[0]=build(k,l,mid-1);
t[k].ch[1]=build(k,mid+1,r);
pushup(k);
return k;
}
inline void rotate(int x){
int y=t[x].fa,z=t[y].fa,k=(t[y].ch[1]==x);
t[x].fa=z,t[z].ch[(t[z].ch[1]==y)]=x;
t[y].ch[k]=t[x].ch[k^1],t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y,t[y].fa=x;
pushup(y);
pushup(x);
}
inline void splay(int x,int g){
pushdown(x);
if(!g) rt=x;
while(t[x].fa!=g){
int y=t[x].fa,z=t[y].fa;
if(z!=g) (x==t[y].ch[0])^(y==t[z].ch[0])?rotate(x):rotate(y);
rotate(x);
}
}
inline int find(int x){
int u=rt;
if(!u) return -1;
while(u){
pushdown(u);
if(t[t[u].ch[0]].siz+1==x){
return u;
}
else if(t[t[u].ch[0]].siz>=x){
u=t[u].ch[0];
}
else{
x-=t[t[u].ch[0]].siz+1;
u=t[u].ch[1];
}
}
return -1;
}
void print(int u){
pushdown(u);
if(t[u].ch[0]) print(t[u].ch[0]);
if(t[u].val>=1&&t[u].val<=n) printf("%d ",t[u].val);
if(t[u].ch[1]) print(t[u].ch[1]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n+2;++i) a[i]=i-1;
rt=build(0,1,n+2);
for(int i=1;i<=m;++i){
int l,r;
scanf("%d%d",&l,&r);
l=find(l),r=find(r+2);
splay(l,0),splay(r,l);
t[t[r].ch[0]].tag^=1;
}
print(rt);
return 0;
}
可持久化平衡树（可持久化FHQ-Treap）
可持久化的思想都是一样的，把改变过的节点存下来以可持久化。
但是在平衡树里结构改变的地方太多了，FHQ稍微少一点但也很多。
splitv，splitsz，merge，pushdown，以及打标记的时候都要可持久化。
特别的，如果不涉及从很久远的版本继承过来进行操作，而是和邻近的版本有关，但是有复制之类的操作时（这个东西在随机数据下是真的，刻意构造就假了），也需要可持久化。这时如果空间很紧，可以设置上限，达到后便线性地重构一下FHQ，释放一下废弃节点。
板子
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
int rd(){
int f=1,r=0;
char ch=gc();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=gc();}
while(isdigit(ch)){ r=(r<<3)+(r<<1)+(ch^48);ch=gc();}
return f*r;
}
mt19937 rnd(19260817);
const int maxn=5e5+10,inf=(1ll<<31)-1;
int n,tot,p,rt[maxn];
struct FHQ{
int rv,val,sz,ch[2];
}t[maxn<<6];
#define ls(u) (t[u].ch[0])
#define rs(u) (t[u].ch[1])
void pushup(int u){
t[u].sz=t[ls(u)].sz+t[rs(u)].sz+1;
}
int newnode(int v){
t[++tot].sz=1;
t[tot].rv=rnd();
t[tot].val=v;
return tot;
}
void splitv(int u,int v,int &l,int &r){
if(!u){
l=r=0;
return;
}
if(t[u].val<=v){
l=++tot;
t[l]=t[u];
splitv(rs(u),v,rs(l),r);
pushup(l);
}
else{
r=++tot;
t[r]=t[u];
splitv(ls(u),v,l,ls(r));
pushup(r);
}
}
void splitsz(int u,int k,int &l,int &r){
if(!u){
l=r=0;
return;
}
if(t[ls(u)].sz+1<=k){
l=++tot;
t[l]=t[u];
splitsz(rs(u),k-t[ls(u)].sz-1,rs(l),r);
pushup(l);
}
else{
r=++tot;
t[r]=t[u];
splitsz(ls(u),k,l,ls(r));
pushup(r);
}
}
void merge(int &u,int l,int r){
if(!l||!r){
u=l+r;
if(u) pushup(u);
return;
}
u=++tot;
if(t[l].rv>t[r].rv){
t[u]=t[l];
merge(rs(u),rs(l),r);
}
else{
t[u]=t[r];
merge(ls(u),l,ls(r));
}
pushup(u);
}
void insert(int x,int &prt){
int rt1=0;
splitv(prt,x,prt,rt1);
merge(prt,prt,newnode(x));
merge(prt,prt,rt1);
}
void del(int x,int &prt){
int rt1=0;
splitv(prt,x,rt1,prt);
int rt2=0;
splitv(rt1,x-1,rt2,rt1);
if(t[rt1].sz) merge(rt1,ls(rt1),rs(rt1));
merge(rt1,rt2,rt1);
merge(prt,rt1,prt);
}
int qryrk(int x,int &prt){
int rt1=0;
splitv(prt,x-1,rt1,prt);
int rs=t[rt1].sz+1;
merge(prt,rt1,prt);
return rs;
}
int qrymx(int u){
if(rs(u)) return qrymx(rs(u));
return t[u].val;
}
int qrymi(int u){
if(ls(u)) return qrymi(ls(u));
return t[u].val;
}
int qryval(int x,int &prt){
int rt1=0;
splitsz(prt,x,rt1,prt);
int rs=qrymx(rt1);
merge(prt,rt1,prt);
return rs;
}
int qrypre(int x,int &prt){
int rt1=0;
splitv(prt,x-1,rt1,prt);
int rs=t[rt1].sz?qrymx(rt1):-inf;
merge(prt,rt1,prt);
return rs;
}
int qrysuf(int x,int &prt){
int rt1=0;
splitv(prt,x,prt,rt1);
int rs=t[rt1].sz?qrymi(rt1):inf;
merge(prt,prt,rt1);
return rs;
}
void solve(){
int v=rd(),op=rd(),x=rd();
rt[++p]=rt[v];
if(op==1) insert(x,rt[p]);
else if(op==2) del(x,rt[p]);
else if(op==3) printf("%d\n",qryrk(x,rt[p]));
else if(op==4) printf("%d\n",qryval(x,rt[p]));
else if(op==5) printf("%d\n",qrypre(x,rt[p]));
else printf("%d\n",qrysuf(x,rt[p]));
}
int main(){
n=rd();
while(n--) solve();
return 0;
}