平衡树（二）
本文中将讲述一下内容：
-
基于
Trie的 类 平衡树（后文称之为BSTrie）
可持久化Treap
可持久化Treap基于FHQ-Treap。其实不难发现，FHQ-Treap在分裂和合并时在每一层只对一个结点产生影响。于是我们可以大胆的可持久化此结构，且保证复杂度为 \(O(\log n\。
其中
(8, 11作为新右树的根，(7, 8作为新左树的根
inline void splitVal(int p, int val, int &x, int &y, bool simple = true {
if (!p return (void(x = y = 0;
int np = simple ? p : clone(p;
if (val(p <= val
x = np, splitVal(rp(p, val, rp(x, y, simple, update(x;
else
y = np, splitVal(lp(p, val, x, lp(y, simple, update(y;
}
simple就是标志是否需要可持久化……特别简单
例如删除操作：
inline int insert(int root, int val, bool simple = false {
int x(0, y(0, p(++usage;
nodes[p].init(val;
splitVal(root, val, x, y, simple;
return merge(merge(x, p, y;
}
这也请读者自行思考为什么不需要合并时可持久化。
基于Trie的 类 平衡树（BSTrie）
说实话，代码无比之简短，并且十分迅速，除了空间复杂度较大之外，令我不禁想要抛弃WBLT……
我们首先只考虑正数的情况。如果我们把每一个数都扩展成同一个位长，从高位向低位保存成一棵树。我们从左到右（认为0在左，而1在右）观察其叶节点所对应的值（类似于Leafy Tree），可以知道是单调递增的，于是我们可以轻易的将之进行魔改，从而做到普通平衡树所能做到的事。
template<int N = 100000>
class BSTrie {
private:
int siz[N << 5];
int ch[N << 5][2];
int usage;
#define newNode( ({ \
++usage; \
siz[usage] = ch[usage][0] = ch[usage][1] = 0; \
usage; \
}
}
这是这一颗树需要用到的内容。其实从这里就应该可以知道，其空间复杂度为 \(O(n \log C\ 其中 \(C\ 表示值域大小，一般为 \(32\。这与其他空间为 \(O(n\ 的平衡树相比远远不如……
插入
void insert(int x {
int p = 1;
for (int i = BS; ~i; --i {
int bt = bit(x, i, &np = ch[p][bt];
if (!np np = newNode(;
p = np, ++siz[p];
}
}
写法有些许迷惑，见谅
由于我们需要用到子树的大小以方便 \(rank, kth\ 操作，所以对于路径上 ++siz[p]
Trie 插入操作吗？不讲了。
删除
void remove(int x {
int p = 1;
for (int i = BS; ~i; --i {
int np = ch[p][bit(x, i];
if (!np return;
p = np;
}
p = 1;
for (int i = BS; ~i; --i {
p = ch[p][bit(x, i], --siz[p];
}
}
这里需要注意的是需要两遍向下，以防止 x 并不存在的情况。
Trie 删除操作类似，想必代码也十分易懂。
查询排名
-
没有子节点，直接返回当前结果
进入右子节点，则累加左子树的大小
int rank(int x, bool within = false {
int p = 1;
int rk = 0;
if (x >= 0 rk += siz[1];
for (int i = BS; ~i; --i {
int bt = bit(x, i, np = ch[p][bt];
if (bt rk += siz[ch[p][0]];
if (!np return rk;
p = np;
}
return within ? rk + siz[p] : rk;
}
这里对于加入了
within参数，用于提示是否需要包含x出现的次数。
查询第k大
呃，令 x 为当前结果：
-
x = (x << 1 | 1（打括号是为了方便理解）
x = x << 1
但是没有这么多个数……则结果不可预测
int kth(int k {
int p = 1;
int x = 0;
for (int i = BS; ~i; --i {
if (k <= siz[lc(p] p = lc(p, x <<= 1;
else k -= siz[lc(p], p = rc(p, x = (x << 1 | 1;
}
return x;
}
于是，你可以在100行内写出一个优秀的平衡树了……
-
第二种方案相对简单，把所有数都加上一个
offset，保证为正整数即可……（这种方法很简答，而且可持久化时也更简单）
依据符号位，建两棵树。根据补码的知识，对于有符号类型的整数，其对应的无符号整型数值越大，其值越大。所以负数也可以利用同样的代码处理。
int p = 1 改为 int p = x < 0 ? 1 : 2（标号随意）即可。
只是在 kth 时，需要有：int x = k <= siz[1] ? (1 << (32 - BS - 1 : 0;
rank 前要多加一句：if (x >= 0 rk += siz[1];
可持久化BSTrie
可持久化 Trie 会吧……OK，下课！
把每一个经过的结点复制出来即可……类比可持久化Treap的操作