# WBLT 小鸡

# Tips:

  • 信息存在叶子上,即 Leafty 性质,每个点维护一个权值 vv ,一个信息大小 sizsiz ,叶子 siz=1,val=vsiz = 1,val=v ,其他点 sizsiz 直接合并,val=val_
    • 这样,点数是 2n2n 的,中序遍历是单调递增的,利用 valval 可实现查值查 rk。
  • 利用单旋和双旋来维护重量平衡
    • 重量平衡大概是搞一个常数 α\alpha ,若左右子树有一个比另一个 α\alpha 还大就不平衡,经论文分析,这样复杂度正确!
  • 写一个内存池来回收删除节点
  • 由于复杂度不是均摊的,容易可持久化

# 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
namespace WBLT {
int ch[N][2], siz[N], val[N];
int pool[N], tot, poolc;
int Id () { return poolc ? pool[poolc--] : ++tot; }
int Recycle (int x) { pool[++poolc] = x; }
int Pushup (int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]];
val[x] = siz[ch[x][1]];
}
int New (int &x, int v) {
x = Id(); ch[x][0] = ch[x][1] = 0, siz[x] = 1, val[x] = v;
}
int Merge (int x, int y) {
int k = Id();
ch[k][0] = x, ch[k][1] = y;
Pushup(k); return k;
}
void Rotate (int x, int op) {
int temp = ch[x][op ^ 1];
ch[x][op ^ 1] = ch[x][op];
ch[x][op] = ch[ch[op ^ 1]][op];
ch[ch[x][op ^ 1]][op] = ch[ch[x][op ^ 1]][op ^ 1];
ch[ch[x][op ^ 1]][op ^ 1] = temp;
Pushup(ch[x][op ^ 1]);
}
const double alpha = 2.;
void Maintain (int x) {
if (siz[ch[x][0]] > siz[ch[x][1]] * alpha) Rotate (x, 0);
else
if (siz[ch[x][1]] > siz[ch[x][0]] * alpha) Rotate (x, 1);
if (siz[ch[x][0]] > siz[ch[x][1]] * alpha) Rotate (ch[x][0], 1), Rotate(x, 0);
else
if (siz[ch[x][1]] > siz[ch[x][0]] * alpha) Rotate (ch[x][1], 0), Rotate (x, 1);
}
void Insert (int &x, int v) {
if (!x) return New(x, v), void();
if (siz[x] == 1) return (x = v > val[x] ? Merge(val[x], v) : Merge(v, val[x])), void();
else Insert(ch[x][v > val[ch[x][0]]], v);
Pushup(x), Maintain(x);
}
void Delete (int &x, int v) {
if ( siz[x] == 1 ) return (Recycle(x), x = 0), void();
int to = v > val[ch[x][0]];
if ( siz[ch[x][to]] == 1 ) Recycle(x), Recycle(ch[x][to]), x = ch[x][to ^ 1];
else Delete (ch[x][to], v), Pushup(x), Maintain(x);
}
int Rank (int x, int v) {
if (siz[x] == 1) return 1;
if (v > val[ch[x][0]]) return siz[ch[x][0]] + Rank(ch[x][1], v);
return Rank(ch[x][0], v);
}
int Find (int x, int v) {
if (siz[x] == v) return val[x];
if (v > siz[ch[x][0]]) return Find(ch[x][1], v - siz[ch[x][0]]);
return Find(ch[x][0], v);
}
}
更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝