[板子/笔记] Treap/Splay/Scapegoat Tree

平衡树啥的学的很迷…瞎写一点好了

Treap

Treap = Tree + Heap.Treap通过给每个节点一个随机的权值,让随机权值满足堆(这份代码是小根堆)的性质,原权值满足二叉树的性质,旋转以维护平衡。

(Luogu P3369)
Code :

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
const int N = 100010,inf = 0x3f3f3f3f;
inline int getint()
{
register int num = 0,sgn = 1;register char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = 0;
for(;isdigit(ch);ch = getchar()) num = (((num << 2) + num) << 1) + (ch ^ '0');return sgn ? num : -num;
}
struct treap
{
int ch[N][2],siz[N],pos[N],w[N],sz = 0,rt = 0;
inline void pushup(int k){siz[k] = siz[ch[k][0]] + siz[ch[k][1]] + 1;}
inline void rotate(int &k,int d){int t = ch[k][d];ch[k][d] = ch[t][!d];ch[t][!d] = k;pushup(k);pushup(t);k = t;}
inline void insert(int &k,int x)
{
if(!k){k = ++sz;siz[k] = 1;pos[k] = rand();w[k] = x;return;}
siz[k]++;int d = x > w[k];insert(ch[k][d],x);if(pos[ch[k][d]] < pos[k])rotate(k,d);
}
inline void remove(int &k,int x)
{
if(w[k] == x)
{
if(!(ch[k][0] && ch[k][1])){k = ch[k][0] | ch[k][1];return;}
int d = pos[ch[k][0]] > pos[ch[k][1]];rotate(k,d);remove(ch[k][!d],x);
}
else remove(ch[k][w[k] <= x],x);
pushup(k);
}
inline int rank(int k,int x)
{
if(!k) return 1;
if(w[k] >= x) return rank(ch[k][0],x);
return rank(ch[k][1],x) + siz[ch[k][0]] + 1;
}
inline int getxth(int k,int x)
{
if(siz[ch[k][0]] == x - 1) return w[k];
if(siz[ch[k][0]] >= x) return getxth(ch[k][0],x);
return getxth(ch[k][1],x - siz[ch[k][0]] - 1);
}
inline int pre(int k,int x)
{
if(!k) return -inf;
if(w[k] < x) return std::max(w[k],pre(ch[k][1],x));
return pre(ch[k][0],x);
}
inline int nex(int k,int x)
{
if(!k) return inf;
if(w[k] > x) return std::min(w[k],nex(ch[k][0],x));
return nex(ch[k][1],x);
}
}T;
int main()
{
int n = getint();
while(n--)
{
int opt = getint(),x = getint();
switch(opt)
{
case 1 : T.insert(T.rt,x);break;
case 2 : T.remove(T.rt,x);break;
case 3 : printf("%d\n",T.rank(T.rt,x));break;
case 4 : printf("%d\n",T.getxth(T.rt,x));break;
case 5 : printf("%d\n",T.pre(T.rt,x));break;
case 6 : printf("%d\n",T.nex(T.rt,x));break;
}
}
return 0;
}


Splay

Splay(伸展树)的主要操作就是把节点通过旋转伸展到根。
Splay(k,g)表示把k旋转到g的儿子。
Splay用的是双旋,一次旋转把k上去2次(单旋叫Spaly)。
Splay能维护区间翻转,让每个节点表示一段区间,翻转时打标记即可。

(Luogu P3391)
Code :

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
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
const int N = 100005,inf = 0x3f3f3f3f;
int a[N];
struct Splay
{
int fa[N],ch[N][2],s[N],rev[N],w[N],rt,sz;
inline void pu(int x){s[x] = s[ch[x][0]] + s[ch[x][1]] + 1;}
inline int dc(int k){return ch[fa[k]][1] == k;}
inline void pd(int x)
{
if(!x || !rev[x]) return;
std::swap(ch[x][0],ch[x][1]);
rev[ch[x][0]] ^= 1;rev[ch[x][1]] ^= 1;rev[x] = 0;
}
inline void rot(int k)
{
int f = fa[k],ff = fa[f],d = dc(k);dk = dc(f);
pd(f);pd(k);
fa[ch[f][d] = ch[k][!d]] = f;
fa[ch[k][!d] = f] = k;
fa[ch[ff][dk] = k] = ff;
pu(f);pu(k);
}
inline int splay(int k,int g)9
{
for(int f,c;(f = fa[k]) != g;rot(k)) if(fa[f] != g) {rot(dc(f) == dc(k) ? f : k);}
if(!g) rt = k;
}
inline int build(int f,int l,int r)
{
if(l > r)return 0;
int mid = (l + r) >> 1,u = ++sz;
w[u] = a[mid];fa[u] = f;rev[u] = 0;
ch[u][0] = build(u,l,mid - 1);
ch[u][1] = build(u,mid + 1,r);
pu(u);
return u;
}
inline int getxth(int x)
{
int u = rt;
while(1)
{
pd(u);
if(x <= s[ch[u][0]]) u = ch[u][0];
else
{
x -= s[ch[u][0]] + 1;
if(!x) return u;
u = ch[u][1];
}
}
}
inline int reverse(int l,int r)
{
l = getxth(l),r = getxth(r + 2);
splay(l,0);splay(r,l);pd(rt);
rev[ch[ch[rt][1]][0]] ^= 1;
}
inline void print(int x)
{
pd(x);
if(ch[x][0]) print(ch[x][0]);
if(w[x] != -inf && w[x] != inf) {printf("%d ",w[x]);}
if(w[ch[x][1]]) print(ch[x][1]);
}
}T;
int main()
{
int n = getint(),m = getint();
for(int i = 1;i <= n;i++) a[i + 1] = i;
a[1] = -inf;a[n + 2] = inf;
T.ch[0][0] = 1;
T.rt = T.build(0,1,n + 2);
while(m--)
{
int x = getint(),y = getint();
T.reverse(x,y);
}
T.print(T.rt);
return 0;
}


Scapegoat Tree

替罪羊树较Treap或Splay来说是一个更暴力的数据结构。
每当一个子树的某子树Size大于子树总Size的某倍(通常为0.7)时,暴力重构子树。
重构过程即是大力拍扁求出它的中序遍历存入数组再build出平衡的子树。

(Luogu P3369)
Code :

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
const int N = 100010,inf = 0x3f3f3f3f;
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct ScapegoatTree
{
const double alpha = 0.7;
int ch[N][2],v[N],siz[N],f[N];int sz,rt;
int buf[N],bz;
ScapegoatTree()
{
sz = 2;rt = 1;
v[1] = -inf;siz[1] = 2;ch[1][1] = 2;
v[2] = inf;siz[2] = 1;f[2] = 1;
}
inline bool balance(int k){return 1.0 * siz[k] * alpha >= 1.0 * siz[ch[k][0]] && 1.0 * siz[k] * alpha >= 1.0 * siz[ch[k][1]];}
inline void dfs(int k)
{
if(ch[k][0]) dfs(ch[k][0]);
buf[++bz] = k;
if(ch[k][1]) dfs(ch[k][1]);
}
int build(int l,int r)
{
if(l > r) return 0;
int mid = (l + r) >> 1,k = buf[mid];
f[ch[k][0] = build(l,mid - 1)] = k;
f[ch[k][1] = build(mid + 1,r)] = k;
siz[k] = siz[ch[k][0]] + siz[ch[k][1]] + 1;
return k;
}
inline void rebuild(int k)
{
bz = 0;dfs(k);
int fa = f[k],d = ch[fa][1] == k;
int r = build(1,bz);
f[ch[fa][d] = r] = fa;
if(k == rt) rt = r;
}
inline void insert(int x)
{
int u = rt,p = ++sz;
siz[p] = 1;v[p] = x;
while(1)
{
siz[u]++;
int d = x >= v[u];
if(ch[u][d]) u = ch[u][d];
else {f[ch[u][d] = p] = u;break;}
}
u = 0;
for(int i = p;i;i = f[i]) if(!balance(i)) u = i;
if(u) rebuild(u);
}
inline int rank(int x)
{
int u = rt,ret = 0;
while(u)
{
if(v[u] < x) ret += siz[ch[u][0]] + 1,u = ch[u][1];
else u = ch[u][0];
}
return ret;
}
inline int getxth(int x)
{
x++;
int u = rt;
while(1)
{
if(siz[ch[u][0]] == x - 1) return v[u];
else if(siz[ch[u][0]] >= x) u = ch[u][0];
else x -= siz[ch[u][0]] + 1,u = ch[u][1];
}
return v[u];
}
inline int find(int x)
{
int u = rt;
while(1)
{
if(v[u] == x) return u;
else u = ch[u][v[u] < x];
}
}
inline void remove(int k)
{
if(ch[k][0] && ch[k][1])
{
int p = ch[k][0];
while(ch[p][1]) p = ch[p][1];
v[k] = v[p];
k = p;
}
int s = ch[k][0] ? ch[k][0] : ch[k][1],d = ch[f[k]][1] == k;
f[ch[f[k]][d] = s] = f[k];
for(int i = f[k];i;i = f[i]) siz[i]--;
if(k == rt) rt = s;
}
inline int pre(int x)
{
int u = rt,ret = -inf;
while(u)
{
if(v[u] < x) ret = std::max(ret,v[u]),u = ch[u][1];
else u = ch[u][0];
}
return ret;
}
inline int nex(int x)
{
int u = rt,ret = inf;
while(u)
{
if(v[u] > x) ret = std::min(ret,v[u]),u = ch[u][0];
else u = ch[u][1];
}
return ret;
}
}T;
int main()
{
int n = getint();
while(n--)
{
int opt = getint(),x = getint();
switch(opt)
{
case 1 : T.insert(x);break;
case 2 : T.remove(T.find(x));break;
case 3 : printf("%d\n",T.rank(x));break;
case 4 : printf("%d\n",T.getxth(x));break;
case 5 : printf("%d\n",T.pre(x));break;
case 6 : printf("%d\n",T.nex(x));break;
}
}
return 0;
}