平衡树

sbt

依靠size域维持平衡,对任意结点$x$满足
$size[rs[x]] \geq size[ls[ls[x]]],size[rs[ls[x]]]$
$size[ls[x]] \geq size[rs[rs[x]]],size[ls[rs[x]]]$


安利退化版sbt,a short introduce
可能被卡(应该不会有人卡这个吧……)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//各种操作,与普通二叉查找树区别不大……
#define son(x,y) c[c[x][y]][y]

inline void pushup(int x){sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;sum[x]=sum[c[x][0]]+sum[c[x][1]]+k[x];}
inline void node(int &x,int v){x=++top,c[x][0]=c[x][1]=0,sz[x]=1,k[x]=v;}

void rotate(int &x,int k)
{
int y=c[x][k^1];
c[x][k^1]=c[y][k];
c[y][k]=x;pushup(y);
pushup(x);x=y;
}

void insert(int &x,int v)
{
if(!x) node(x,v);
else
{
bool m=v>=k[x];//这里把相同元素插入x的右子树
insert(c[x][m],v);
if(sz[son(x,m)]>sz[c[x][m^1]])//维护平衡
rotate(x,m^1);
}
pushup(x);
}

int pre(int x,int y,int v)
{
if(!x) return y;
if(v>k[x]) return pre(c[x][1],x,v);
return pre(c[x][0],y,v);
}

int suc(int x,int y,int v)
{
if(!x) return y;
if(v<k[x]) return suc(c[x][0],x,v);
return suc(c[x][1],y,v);
}

int rk(int x,int v)//求权值为x的排名
{
if(!x) return 1;
if(v>k[x]) return sz[c[x][0]]+1+rk(c[x][1],v);
return rk(c[x][0],v);
}

int select(int &x,int w)
{
int r=sz[c[x][0]]+1;
if(w<r) return select(c[x][0],w);
if(w>r) return select(c[x][1],w-r);
return k[x];
}

void del(int &x,int v){
if(!x) return ;sz[x]--;sum[x]-=v;
if(k[x]!=v) del(c[x][v>k[x]],v);
else
{
int l=c[x][0],r=c[x][1];
if(!l||!r) x=l+r;
else {
while(c[r][0]) r=c[r][0];//乱搞删除
k[x]=k[r];
del(c[x][1],k[r]);
}
}
}

void init(){
x=0,top=0;
}


splay

依靠伸展操作维护平衡,复杂度可以势能分析证明
使被查询频率高的节点更靠近树根
常数巨大


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//LCT
inline bool f(int x){return c[fa[x]][1]==x;}//指示方向

inline bool isr(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}

void pushdown(int x)
{
if(!rev[x]) return ;
int &l=c[x][0],&r=c[x][1];
rev[l]^=1;rev[r]^=1;swap(l,r);
rev[x]=0;
}

void rotate(int x)
{
int p=fa[x],g=fa[p],r;
bool k=f(x),m=f(p);r=c[x][k^1];
if(!isr(p)) c[g][m]=x;//自上而下重新连接
fa[x]=g,c[x][k^1]=p;
fa[p]=x,c[p][k]=r;
if(r) fa[r]=p;
}

void maintain(int x)
{
int top=0;st[++top]=x;
for(int i=x;!isr(i);i=fa[i]) st[++top]=fa[i];
for(int i=top;i;i--) pushdown(st[i]);
}

void splay(int x)
{
maintain(x);
for(;!isr(x);rotate(x))
if(!isr(fa[x])) rotate(f(x)==f(fa[x])?fa[x]:x);//理性理解
}


fhq treap

每个结点有一个附加权,满足堆的性质
随机生产附加权,达到期望平衡
非旋转,可持久化


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int merge(int x,int y)
{
if(!x||!y) return x+y;
pushdown(x);pushdown(y);
if(rk[x]<rk[y])
{
c[x][1]=merge(c[x][1],y);
pushup(x);
return x;
}
else
{
c[y][0]=merge(x,c[y][0]);
pushup(y);
return y;
}
}

void split(int now,int k,int &x,int &y)//按前k个分裂
{
if(!now) x=y=0;
else
{
pushdown(now);
if(k<=size[c[now][0]])
y=now,split(c[now][0],k,x,c[now][0]);
else
x=now,split(c[now][1],k-size[c[now][0]]-1,c[now][1],y);
pushup(now);
}
}

link1
link2

分享到: