WBLT 小记
综述
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}$ 和 $\text{rotate}$ 操作不可区分。——lxl
下面给出 $\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
言归正传。这一做法的复杂度证明依赖于这一结论：
在合并过程中，每递归一层，$\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}$。
对于上面的第一、二种情况，合并过程直接结束。
对于第三种情况，我们有：
$$ \begin{aligned} &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 \\ \end{aligned} $$
对于第四种情况：
对于前两次合并，我们有：
$$ \begin{aligned} &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) \end{aligned} $$
对于最后一次合并，我们有：
$$ \begin{aligned} 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} \end{aligned} $$
直接把分子上的 $y$ 放到 $x$，把分母上的 $y$ 放到 $0$，可以发现这个柿子是 $O(1)$ 级别的。
但是这里带着大 $O$ 归纳，以及没有讨论递归下去的使用两个子树大小关系发生变化的情况，因此并不是特别严谨。
有结论：$\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