[DS-3] WBLT 小记

Moeebius · 2024-02-05 21:29:16 · 算法·理论

综述

WBLT (Weight Balanced Leafy Tree, a.k.a \text{BB}[\alpha] tree) 是一种满足重量平衡性质的平衡树，最大优势在于良好的平衡性质和对可持久化的高度支持。

下面给出重量平衡和 Leafy 平衡树的定义：

一棵树是 （广义）重量平衡 的，当且仅当从任意节点向上走 O(1) 步后，节点所在子树大小能翻常数倍。容易发现，满足重量平衡性质的树树高为 O(\log n)。

一棵 Leafy 的平衡树所有信息都存储在叶子节点处，非叶节点 p 恰好有两个儿子 lc_p, rc_p，且存储两个儿子节点信息合并后的结果。

对于 WBLT：

定义子树大小 \text{size}_p 为 p 子树内叶子节点个数。
定义平衡常数 \alpha，要求 \forall p, \min\{\text{size}_{lc_p},\text{size}_{rc_p}\}\ge \alpha\ \text{size}_p。一般取 \alpha \approx 1-\frac{\sqrt2}{2}。

容易发现，WBLT 满足重量平衡的性质。

合并与分裂

下面给出 \text{merge} 操作的做法：

设当前要合并的两树根节点为 p 和 q，且 p 中元素均小于 q 中元素。

下面仅讨论 \text{size}_p \ge \text{size}_q 的情况。

如果 p,q 之一为空，直接返回。
如果 \text{size}_q \ge \alpha(\text{size}_p + \text{size}_q)：直接新建一个节点 o，将 o 的左右儿子分别设为 p 和 q，并返回。
否则，如果 \text{size}_{lc_p} \ge \alpha(\text{size}_p + \text{size}_q)：递归合并 rc_p 和 q，并将合并得到的节点设为 rc_p。
否则，递归合并 lc_p 和 lc_{rc_p}，递归合并 rc_{rc_p} 和 q，并将得到的两个节点 递归合并。（此外，另一种写法是把第一次合并换成左旋，实际上是等价的）

容易发现，这样得到的 WBLT 依然平衡。

对于第 4 类情况，一种广为人知的错误写法是直接将得到的两个节点作为左右儿子。这样可能会造成左儿子大小大于 (1-\alpha) 倍的总大小，从而导致 WBLT 失衡。

笔者发现，以下讲稿的 merge 操作都是错误的。

~~https://www.luogu.com.cn/blog/piggyBlog/wblt-xiao-ji~~（目前已经修正）

https://www.luogu.com.cn/blog/qwaszx/leafy-tree-hu-wblt-xue-xi-bi-ji

https://www.luogu.com.cn/blog/lrcwbbBlog/fight-against-fhq

言归正传。这一做法的复杂度证明依赖于这一结论：

在合并过程中，每递归一层，\dfrac{\text{size}_p}{\text{size}_q} 的值下降常数倍。（这里依然认为 \text{size}_p \ge \text{size}_q，相反的情况同理）

Proof:

记 x= \text{size}_p,y=\text{size}_q，且下文中的 lc,rc 等均指代对应节点的 \text{size}。

对于上面的第一、二种情况，合并过程直接结束。

对于第三种情况，我们有：

lc_x \ge \alpha (x+y) \\ \implies rc_x=x-lc_x \le (1-\alpha)x-\alpha y \\ \implies \frac{rc_x}{y} \le \frac{(1-\alpha)x-\alpha y}{y} = (1-\alpha)\frac{x}{y}-\alpha \\

对于第四种情况：

对于前两次合并，我们有：

lc_x \ge \alpha x \\ \implies rc_x \le (1-\alpha)x \\ \implies rc_{rc_x},lc_{rc_x} \le (1-\alpha)^2x \\ \implies \frac{rc_{rc_x}}{y} \le (1-\alpha)^2 \frac{x}{y}, \frac{lc_{rc_x}}{lc_x} \le \frac{(1-\alpha)^2}{\alpha}=O(1)

对于最后一次合并，我们有：

lc_x + lc_{rc_x} \le \alpha^2(x+y) + (1-\alpha)x \\ rc_{rc_x} + y \ge (x - lc_x - lc_{rc_x}) + y \\ \implies \frac{lc_x+lc_{rc_x}}{rc_{rc_x}+y} \le \frac{\alpha^2(x+y)+(1-\alpha)x}{x+y-(\alpha^2(x+y)+(1-\alpha)x)+y} \\ =\frac{(\alpha^2-\alpha+1)x+\alpha^2y}{(-\alpha^2+\alpha)x+(2-\alpha^2)y}

直接把分子上的 y 放到 x，把分母上的 y 放到 0，可以发现这个柿子是 O(1) 级别的。

证毕。

由此，我们可以得出 \text{merge} 操作的复杂度为 O(\frac{\text{maxSize}}{\text{minSize}})。

至于 \text{split} 操作，我们可以直接使用类似线段树的分治做法，并将子节点 \text{split} 得到的树 \text{merge} 起来。得益于 \text{merge} 的优秀性质，这样做复杂度是 1log 的，证明先咕了。

单旋与双旋

先咕了，可以见这里。

插入、删除与平衡维护

维护平衡有三种方式，一种是重构，一种是旋转，一种是合并。

注意到，每次插入/删除一个点后，可能失衡的点只在一条链上，依次判断即可。

重构：类似替罪羊树的写法，均摊 O(\log n)。
旋转：严格 O(\log n)。
合并：如果发现失去平衡，则调用 \text{merge(lc}_p,\text{rc}_p)。注意到合并两子树大小之比是常数，所以复杂度依然是严格 O(\log n) 的。

注意到我们最好进行垃圾回收，不然空间常数较大。

持久化

WBLT 是父亲认儿子，儿子不认父亲的优秀结构，因此直接上路径复制即可。

注意到如果要保存所有的历史版本，WBLT 的空间并不劣。如果只需要最后一份版本（常见于区间复制等场景），且序列长度始终与 n 同阶，可以考虑在 O(\frac{n}{\log n}) 次后重构并回收空间。

例题

Luogu P5055:

维护序列，支持区间翻转、单点插入、单点删除、区间求和，强制在线并要求完全持久化。常识范围。

sol：直接上持久化 WBLT。另外这道题可以不打 tag，维护一正一反两棵 WBLT。复杂度 O(m \log n)。

Luogu P8263:

维护 01 序列，支持区间复制 k 次、区间翻转复制 k 次（是否翻转取决于重复次数的 \text{popcount}），区间删除，查找第 k 个 1 的出现位置。常识范围，保证任意时刻序列长度不超过 10^8。

sol：直接上持久化 WBLT。

如果你需要打 tag，记得下传标记前新建节点。
复制 k 次时需要倍增。由于 WBLT 的优秀特性，总复杂度依然是一只 \log 的。

PKUWC 2024 D2T3

维护一个序列，每个元素是一个栈，支持区间 push k 个相同的数，区间 pop k 次（如果已经为空就忽略），单点查栈中 [l,r] 区间和。序列长度、操作数、push 时数量、push 的值不超过 10^5，pop 和区间和时参数不超过 10^{10}。

sol：把相同的数直接看作一个值，直接上线段树套持久化 WBLT。

懒标记维护 (先要删除的数、之后要加入的数)。容易发现这样标记是可以合并的。
空间记得开大！

总复杂度 O(m \log ^2 n)。

Luogu P7739

比较长，转化后的题意是有两种矩阵，维护全局矩阵乘积，要求支持「区间 reverse」、「区间 flip（即区间内所有位置改为另一种矩阵）」和尾部插入。

sol：直接上 WBLT，每个节点维护当前区间内原答案、flip 后答案、reverse 后答案和 flip+reverse 后答案，并且维护 flip 和 reverse 标记。

尾部插入和区间 flip 是好维护的；区间 reverse 的话先 split 出区间、打上 tag，再 merge 回去。

复杂度 1log，写 FHQ 可能会被卡常，但是 WBLT 稳过！！！111