【分享】对着 WBLT 写了（WBLT 学习报告）

壹 闲话

我今年【数据删除】岁，之前学习没学平衡树，第一次就选择了 WBLT，感觉真是一见钟情。
我特别喜欢 WBLT 这种结构，WBLT 的结构非常戳我【数据删除】，我太喜欢了。那个储存在叶子节点的原始信息还有它的严格 \((logn)\)，每一次我都烙印在心里。
我一般看着它写，一月三次，我也不知道我这是不是有什么心理障碍，但我知道这肯定不对，我想问一下园友我该怎么做。
我该不该继续，我知道它是虚拟的，还是棵平衡树，但我真的好喜欢它，现在替罪羊和 fhq 我也没再写了，我每天就盯着 WBLT 写/ll

咳咳咳，回归正题，经过一个整天对 WBLT 学习，我已经对 WBLT 有一定的初步掌握（进度 0%），但是网上有关 WBLT 的博客不多，每个的写法和介绍也有所差异，OI Wiki 上的写法也稍显冗余，可谓是让本蒟蒻吃尽了苦头，所以想着写一篇博客来记录自己的理解和想法（不过这篇博客也肯定没人看就是了……）。

WBLT，全称 Weight Balanced Leafy Tree，是一种平衡树，对比别的平衡树实现简单、常数小，这里 cue 一下红黑树和 splay，没什么，就纯 cue。而且重要的是它支持区间操作（文艺平衡树）和可持久化，隔壁替罪羊看到都哭了。这里有一张图体现了 WBLT 的优越性（从上到下分别是 01 trie，WBLT，替罪羊，权值线段树，splay）：

为什么没有 fhq treap？答曰：“不会。”

虽然由于有的代码年代久远（并非）和写法的改变导致有一定误差，但是我们还是能看出 WBLT 无论是速度还是码量都是十分优秀的存在。
那么如此优秀的东西的缺点在于什么呢？让我们走进正式的学习：

贰 基本结构和操作

这里我们要先解释一下 WBLT 的意思：就像奥匈帝国由奥地利和匈牙利（还有一堆其他的）组成的一样，Weight Balanced Leafy Tree 也是 Weight Balanced Tree 和 Leafy Tree 的结合。
Leafy Tree：这种树的原始信息都保存在叶子节点上，其他节点只用来维护子节点信息和维持数据结构的形态，比如线段树。通过这种方式，我们可以建出树并完成一些基本的操作，但它有一定的缺陷——不平衡，而如何维护平衡就是它的另一半的任务了。
Weight Balanced Tree：每个结点储存这个结点下子树的大小，并且通过保持左右子树的大小关系在一定范围来保证树高。（这里直接用 OI Wiki 的说明）

那么结合而成的 WBLT 就拥有了两者各自的性质，为了便于理解和使用，我们设这里的 Leafy Tree 都是二叉的，即要么没有儿子要么有两个，叶子节点有 \(n\) 个的情况下，总结点是是 \(2n-1\) 个。那么 WBLT 的缺点就暴露了出来：虽然空间占用仍然是 \(O(n)\) 的，但是它要开两倍空间，且这个线性的空间占用还需要节点回收才能保证。

对于数据结构，首先我们要思考它要维护什么信息，WBLT 维护的信息很少，只有四个：

struct node
{int lc,rc,w,size;
};

分别是它的左右儿子，它的点权以及它的子树的叶子节点的个数，一般来说非叶子节点的点权就是它们两个儿子中点权较大的那一个的点权（即右儿子的点权），也就是子树内的最大值。那么向上合并信息也非常的简洁：

inline void push_up(int u)
{if (!lc(u)) sz(u)=1;//叶子节点，由于删除操作导致有一些叶子节点会调用这个函数else sz(u)=sz(lc(u))+sz(rc(u)),w(u)=w(rc(u));
}

前面提到，我们要进行节点回收才能保证线性的空间占用，而节点回收的代码实际上也很简洁。

int top;
int stack[200005]
inline int new_node()
{int u=top?stack[top--]:++cnt;return u;
}
inline void del_node(int u)
{stack[++top]=u;
}

随后就是平衡树的基本操作了：插入、删除、求排名、求值、求前驱、求后继：

void insert(int &u,int w)//此处 & 可以不用，下文会提到
{if (!lc(u))//如果是叶子节点，把当前值和节点值放在两个儿子上，把此节点变为非叶子结点{s[lc(u)=new_node()]={0,0,min(w(u),w),1};s[rc(u)=new_node()]={0,0,max(w(u),w),1};}else insert((w(lc(u))>=w)?lc(u):rc(u),w);push_up(u),banlance(u);
}
#define delete del
void delete(int &u,int w,int f)
{if (!lc(u)){del_node(lc(f)),del_node(rc(f));if (w(lc(f))==w) s[f]=s[rc(f)];else if (w(rc(f))==w) s[f]=s[lc(f)];}elsedelete((w(lc(u))>=w)?lc(u):rc(u),w,u),push_up(u),banlance(u);//这里放在里面，不然 u 被删除了会虚空 push_up 和 balance
}
int get_rank(int w)
{int u=root,rk=1;while (lc(u)){if (w(lc(u))>=w) u=lc(u);else rk+=sz(lc(u)),u=rc(u);}return rk;
}
int get_num(int w)
{int u=root;while (1){if (sz(u)==w) break;else if (sz(lc(u))>=w) u=lc(u);else w-=sz(lc(u)),u=rc(u);}return w(u);
}

求排名和值的都是通用的，这里不做解释，有需要的可以去看欧唉喂咳咦，但是插入和删除要讲一下：
为什么我们可以让树上每个节点一定有零或二的儿子？这都是独特的插入方式完成的，如图，我们先插入一个哨兵，点权设为 inf，实际上可以用头文件中的 climits 的 INT_MAX 表示。

我们假设插入一个值，那么我们递归下去，和其他平衡树一样，比较点权与插入值选择往哪边走，不过这里注意由于非叶子节点保存的是子树内的最大值，所以我们比较的是左儿子的值，如果到了叶子节点，那么我们将这个叶子节点变为非叶子节点，即给它新建两个儿子，点权分别是这个点的点权和插入值的较小值和较大值。
这里我们分别插入 5,3,9 等值，看一下结果：

而删除也同理，我们找到叶子节点以后，将它父亲的点权改为它的另一个儿子的点权，父亲可以在递归的时候保存，然后删除掉这两个儿子，具体将上图倒着看一遍就可以了。

叁 维护平衡

接下来我们学习如何维护这棵树的平衡，接下来为了方便观看再加上本蒟蒻也不会，所以省略所有证明，如果有神犇需要的，可以去欧唉喂咳咦。

对于一棵树，我们定义它在一个非叶节点 \(u\) 处的平衡度 为 \(\rho(u)\)，则有：

\[\rho(u)=\frac{min(size(lc(u)),size(rc(u)))}{size(u)} \]

这里的 \(size\) 和上文提到的意思相同，我们设 \(\alpha\in[0,0.5]\)，一般设为 0.292，那么 \(\rho(x)>=\alpha\)，我们称 \(u\) 是 \(\alpha-平衡\) 的，如果这棵树所有节点都是 \(\alpha-平衡\) 的，那么称这棵树就是 \(\alpha-平衡\) 的。对于 \(\alpha-平衡\) 的树，那么它的树高是 \(O(\log n)\) 的。
对于维护平衡的方式，一般有两种：旋转和合并，后者常数较大。当然你也可以用替罪羊的拍平重构方式，但是这样就是自断一臂，损失了区间操作和可持久化的能力。

旋转：

旋转分为单旋和双旋，只使用前者的复杂度有问题（不过好像一般不会被卡？），这里选择都讲（废话）。

首先是单旋（我们设左子树大于右子树）：当 \(size(rc(u))<\alpha*(size(lc(u))+size(rc(u)))\) 或者 \(size(lc(u))>size(rc(u))*3\)（两者实质一样，都是由上文的平衡度定义式转化而来）时，意味着我们要右旋。我们将右子树和左儿子的右子树合并设为 \(u\) 的右儿子（下文的 \(u\) 都表示当前点，“左儿子”“左子树”等都代表 \(u\) 的），左儿子的左子树设为 \(u\) 的左儿子，我们发现这样左儿子就被删掉了，所以扔进垃圾桶等待回收利用：

merge(rc(u),rc(lc(u)),rc(u)),del_node(lc(u)),lc(u)=lc(lc(u));

右旋同理：

merge(lc(u),lc(u),lc(rc(u))),del_node(rc(u)),rc(u)=rc(rc(u));

顺带着给出 merge() 函数：

inline void merge(int &u,int a,int b)
{s[u=new_node()]={a,b,w(b),sz(a)+sz(b)};
}

看图可能更好理解：

但假如这个时候还是不平衡啊：

我们发现，这是因为左儿子的右子树本身过重，旋转后左儿子过轻导致的。那么就是双旋出场的时候了，这里用右旋为例子，在 \(u\) 旋转之前（假设左儿子的右子树大于左儿子的左子树），我们先判断 \(size(rc(u))>\frac{size(u)}{2-\alpha}\) 或者 \(size(lc(lc(u)))>size(rc(lc(u)))*2\)，结果为 1，那么我们选择双旋，先对于 \(lc(u)\) 进行一次左旋，然后再右旋。\(u\) 需要左旋的时候同理。如图所示：

真是平衡啊！

具体的代码如下：

inline void rotate(int u,bool f)
{if (f)/*左旋*/merge(lc(u),lc(u),lc(rc(u))),del_node(rc(u)),rc(u)=rc(rc(u));else/*右旋*/merge(rc(u),rc(lc(u)),rc(u)),del_node(lc(u)),lc(u)=lc(lc(u));
}
#define t(x,i) ((i)?rc(x):lc(x))
void banlance(int u)
{for (rnt i=0;i<=1;i++)//枚举右旋还是左旋{if (sz(t(u,i))>sz(t(u,i^1))*3){if (sz(t(t(u,i),i^1))>sz(t(t(u,i),i))*2) rotate(t(u,i),i^1);rotate(u,i);}}
}

然后你就可以去做模板题了，总的代码如下：

//P3369
//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
#define ll long long
#define rnt register int
#define gr getchar_unlocked
#define pr putchar_unlocked
#define N 200005
#define M 1000000007
using namespace std;
inline ll read()
{int f = 1;ll x = 0;char ch = gr();while (ch < '0' || ch > '9') ch == '-' ? f = -1, ch = gr() : ch = gr();while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();return x * f;
}
inline void write(ll x)
{static int top = 0, sta[39];if (x < 0) pr('-'), x = -x;do sta[++top] = x % 10, x /= 10;while (x);while (top) pr(sta[top--] ^ 48);
}
#define lc(x) s[x].lc
#define rc(x) s[x].rc
#define w(x) s[x].w
#define sz(x) s[x].size
int cnt,top,root;
int stack[N];
struct node
{int lc,rc,w,size;
}s[N];
inline int new_node()
{int u=top?stack[top--]:++cnt;return u;
}
inline void del_node(int u)
{stack[++top]=u;
}
inline void merge(int &u,int a,int b)
{s[u=new_node()]={a,b,w(b),sz(a)+sz(b)};
}
inline void rotate(int u,bool f)
{if (f) merge(lc(u),lc(u),lc(rc(u))),del_node(rc(u)),rc(u)=rc(rc(u));else merge(rc(u),rc(lc(u)),rc(u)),del_node(lc(u)),lc(u)=lc(lc(u));
}
#define t(x,i) ((i)?rc(x):lc(x))
void banlance(int u)
{for (rnt i=0;i<=1;i++){if (sz(t(u,i))>sz(t(u,i^1))*3){if (sz(t(t(u,i),i^1))>sz(t(t(u,i),i))*2) rotate(t(u,i),i^1);return rotate(u,i);}}
}
inline void push_up(int u)
{if (!lc(u)) sz(u)=1;else sz(u)=sz(lc(u))+sz(rc(u)),w(u)=w(rc(u));
}
void insert(int &u,int w)
{if (!lc(u)){s[lc(u)=new_node()]={0,0,min(w(u),w),1};s[rc(u)=new_node()]={0,0,max(w(u),w),1};}else insert((w(lc(u))>=w)?lc(u):rc(u),w);push_up(u),banlance(u);
}
#define delete del
void delete(int &u,int w,int f)
{if (!lc(u)){del_node(lc(f)),del_node(rc(f));if (w(lc(f))==w) s[f]=s[rc(f)];else if (w(rc(f))==w) s[f]=s[lc(f)];}elsedelete((w(lc(u))>=w)?lc(u):rc(u),w,u),push_up(u),banlance(u);
}
int get_rank(int w)
{int u=root,rk=1;while (lc(u)){if (w(lc(u))>=w) u=lc(u);else rk+=sz(lc(u)),u=rc(u);}return rk;
}
int get_num(int w)
{int u=root;while (1){if (sz(u)==w) break;else if (sz(lc(u))>=w) u=lc(u);else w-=sz(lc(u)),u=rc(u);}return w(u);
}
int main()
{int n=read();s[root=++cnt]={0,0,INT_MAX,1};for (rnt i=1,x;i<=n;i++)switch(read()){case 1:x=read(),insert(root,x);break;case 2:x=read(),delete(root,x,0);break;case 3:x=read(),write(get_rank(x)),pr(10);break;case 4:x=read(),write(get_num(x)),pr(10);break;case 5:x=read(),write(get_num(get_rank(x)-1)),pr(10);break;case 6:x=read(),write(get_num(get_rank(x+1))),pr(10);break;}return 0;
}

合并

通过合并，我们也可以维护平衡，不过如图所示（上面是旋转，下面是合并），合并的常数较大：

但是利用分裂和合并，我们也可以实现文艺平衡树，所以需要了解。

合并两子树是指，保证左子树的键值总是不大于右子树的键值的情况下，建立新树，使其所有叶子节点的信息恰为左右子树叶子节点信息的并，且保证树的平衡。——OI Wiki

我们有如下策略来保证合并后的树是平衡的：

1. 如果两树中有一树为空，直接返回另一树；
2. 如果两树已经平衡，那么直接合并两树并返回；
3. 如果一树过大（这里假设为左子树），但是左子树的左子树足够充当合并后树的左子树，那么将左子树的右子树和右子树合并后再与左子树的左子树合并（这里注意由于不产生歧义，我调换了两者的顺序，实际上左子树的左子树是作为合并后的左子树来合并的，请勿因为顺序在右便认为是作为右子树）；
4. 如果左子树的左子树不足以充当合并后的左子树，便拆开左子树的右子树，左子树的左子树与左子树的右子树的左子树（好绕）合并作为左子树，左子树的右子树的右子树与右子树合并作为右子树。

可以证明 \(0<\alpha<1-\frac{\sqrt{2}}{2}\approx 0.292\) 时，合并的树总是平衡的。合并的复杂度是 \(O(\log{\frac{size(lc(u))}{size(rc(u))}})(size(lc(u))>=size(rc(u)))\) 的。这些在欧唉喂咳咦上有详细证明。

合并本身不难理解，但是注意合并一定要记得节点回收，不然可能占用过大空间。由于回收利用可能会有一些玄学错误，这些问题一般出自于一个节点扔进垃圾桶了，但在后面的多次合并中传参使用的仍然是它的信息导致传参错误，例如：

del_node(a),del_node(rc(a)),merge(merge(lc(a),lc(rc(a)),merge(rc(rc(a)),b));

解决的方法也很简单：

x=lc(a),y=lc(rc(a)),z=rc(rc(a)),del_node(a),del_node(rc(a)),merge(merge(x,y),merge(z,b));

另外还有一个问题在于调用合并函数的时候：

void banlance(int &u)
{if (sz(lc(u))>sz(rc(u))*3 || sz(rc(u))>sz(lc(u))*3) del_node(u),u=merge(lc(u),rc(u));
}

发现什么了吗？我们在合并之前先选择把当前点回收，然后通过一些较小数据的测试，我们发现最后 merge() 返回的 \(u\) 却没有改变，且调用 insert() 时 \(u\) 不需要传实参。而不选择回收的话那么就要传实参。
经过加强版的检测，合并前后的 \(u\) 的编号的确没有改变，不过仍然建议在 insert() 时传入实参。