WBLT 入门

· · 个人记录

缘起

yummy 想学会写平衡树，但是他觉得 Treap 比较抽象，Splay 里面每个元素的地位不平等（有的是叶子，有的是分界点）比较难以管理，而红黑树又超级麻烦，于是平衡树这事搁置了三年。

你可能会问，没有平衡树的三年 yummy 都是怎么过来的——

首先就是著名的模板题 P3369 —— 这道题 yummy 已经完成了 vector 做法，学习了 pbds 的用法。前两天 yummy 看到自己一年前的 01 trie 做法，然后花了一下午把它调试完成并 AC 了。

但是 pbds 背不下来，能维护的操作也有限。yummy 觉得， 01 trie 的空间比较大是它很大的弊端，如果用它写树套树板板题，那么会 MLE，也就会促进我学平衡树。后来嘛，我把指针改成了数组下标，通过了。

然后就看到了文艺平衡树，发现 01 Trie 不能维护下标，这才意识到，必须学一种数据结构了。

打开平衡树板板的加强版，有 Treap，Splay，压缩版 01 Trie... 还有... WBLT？这是什么？

看了看作者，是可爱的 BF。仔细看了看 WBLT 简介，发现它非常像线段树，简直就是我梦中情数据结构！于是我决定我的第一棵平衡树就写 WBLT 了！

本文会按照 yummy 自认为的逻辑顺序讲解，更多时候也是给自己看的。

前置知识：线段树。

基本操作

WBLT，全称 Weight-Balanced Leafy Tree：

节点保存的信息

首先我们需要建一棵 Leafy Tree。这棵树的叶子从左到右权值逐渐增加。

接下来考虑如果要查找一个数 p，如何判断它在根的左边还是右边——如果 p 比左子树最大的数还大，那么就往右子树走，否则往左子树走。因此，对于每个节点，我们要维护该点为根的子树最大值 val。

同时，为了给 Weight Balanced 作准备以及求排名，我们也要记录每个点为根的子树节点数 sz。

int n,m,used;
struct node
{
    int sz,val,lson,rson;
}a[8000005];//数组不要钱，别 MLE 就行
int New(int val){//新建一个叶子
    used++;a[used]=(node){1,val,0,0};return used;}
int New(int ls,int rs){//新建一个非叶节点，左右孩子是 ls 和 rs
    used++;a[used]=(node){a[ls].sz+a[rs].sz,a[rs].val,ls,rs};return used;}

我们注意到，因为只有叶子是单点信息，因此 n 个数的集合需要 (2n-1) 个节点维护。

给值求排名

自然地，如果要求值的数比左孩子 val 更大那么这个值在右子树，并且它大过左子树所有数；否则在左子树里继续查找。

int rnk(int rt,int val)//返回的排名从 0 开始数
{
    if(a[rt].sz==1)
        return val>a[rt].val;
    if(val>a[a[rt].lson].val)
        return a[a[rt].lson].sz+rnk(a[rt].rson,val);
    else return rnk(a[rt].lson,val);
}

给排名求值

如果要求的名次左子树节点数不够，那么在右子树继续找，否则在左子树里面找。

int xth(int rt,int x)
{
    if(a[rt].sz==1)
        return a[rt].val;
    if(x>=a[a[rt].lson].sz)
        return xth(a[rt].rson,x-a[a[rt].lson].sz);
    return xth(a[rt].lson,x);
}

加入节点

首先查找这个数，找到离这个数最近的叶子节点之后，新建一个分叉节点，把这个叶子和要插入的数一起塞进去，然后要求这个叶子本来的父亲指向新的分叉节点。

注意到连续多次往同一个地方插入节点可能导致层数过多，因此加入接点后我们需要平衡一下。后文会详细解释。

int insert(int rt,int val)//returing val == new root 
{
    if(a[rt].sz==1)//发现rt就是需要插入的叶子节点
    {
        int nson=New(val);
        if(val<a[rt].val)
            return New(nson,rt);//将叶子和新点一起塞进去，并要求父亲指向它，下同
        else
            return New(rt,nson);
    }
    a[rt].sz++;
    if(val>a[a[rt].lson].val)
    {
        a[rt].rson=insert(a[rt].rson,val);//如果往右子树插入节点，可能会导致 val 有变化，务必注意
        a[rt].val=a[a[rt].rson].val;
    }
    else
        a[rt].lson=insert(a[rt].lson,val);
    bal(rt);//一会儿实现
    return rt;
}

删除节点

可以看作加入节点的逆过程。每次找到其中一个孩子是要删去的节点的 rt 时，直接要求父亲指向这个分叉口的另一个孩子。

注意，这里不能理解成“碰到两个孩子都是叶子”的 rt，因为曾经同为叶子的点可能已经被分叉点取代。

int erase(int rt,int val)//returning val == new root
{
    if(a[rt].sz==1)//如果是叶子那么标记特殊情况
        return 0;
    a[rt].sz--;
    if(val>a[a[rt].lson].val)//向右找
    {
        a[rt].rson=erase(a[rt].rson,val);
        a[rt].val=a[a[rt].rson].val;//如果删的是右子树节点那么 val 可能更新
        if(a[rt].rson==0)//如果右孩子是叶子
            return a[rt].lson;//那么直接要求父亲指向左节点
    }
    else
    {
        a[rt].lson=erase(a[rt].lson,val);
        if(a[rt].lson==0)
            return a[rt].rson;
    }
    bal(rt);
    return rt;
}

平衡

当一侧节点过多时，我们可以要求调整树的形态。一般认为一侧是另一侧节点数的 4 倍以上需要平衡。

如果右子树节点过多，我们可以把右孩子的左子树加入到左孩子那边。这种平衡的写法和加入单个节点差不多。

yummy 写这一段的时候，注意到右孩子的左子树被挖了后被丢弃了，而左子树需要新建一个分叉口承载原来的左子树和搬过来的右子树的左子树，因此我们可以把丢弃的节点拿过来使用。

以上体现了右子树过大时如何进行平衡。下面是代码实现（其中 K 是常数 4，建议对着图看代码）：

void bal(int rt)
{
    if(a[a[rt].rson].sz>a[a[rt].lson].sz*K)
    {
        int Aid=a[rt].lson,Bid=a[rt].rson;//没错就是图上的 A 和 B
        a[rt].lson=Bid;
        a[rt].rson=a[Bid].rson;
        a[Bid].rson=a[Bid].lson;
        a[Bid].lson=Aid;
        a[Bid].sz=a[a[Bid].lson].sz+a[a[Bid].rson].sz;
        a[Bid].val=a[a[Bid].rson].val;
    }
    else if(a[a[rt].lson].sz>a[a[rt].rson].sz*K)
    {
        int Aid=a[rt].rson,Bid=a[rt].lson;
        a[rt].rson=Bid;
        a[rt].lson=a[Bid].lson;
        a[Bid].lson=a[Bid].rson;
        a[Bid].rson=Aid;
        a[Bid].sz=a[a[Bid].lson].sz+a[a[Bid].rson].sz;
        a[Bid].val=a[a[Bid].rson].val;
    }
}

注意事项

有的时候整棵树会被删空，因为根节点没有父亲，可能会出现一些意外，而且根节点“要求父亲连向返回值”会被忽略。因此，一种推荐做法是提前丢一个 \inf 进去，然后对于加入和删除操作记录更新之后的新根。

至于为啥时间复杂度是对的？因为每向下一层节点，子树大小至少乘以 0.8，因此树高是 O(\log n) 的。

下面给出 P6136 我的完整代码：Here!

重头戏：文艺平衡树（P3391）

我没有找到用 WBLT 维护区间翻转的题解，题解区最多的是 Splay，然后是分块，最少的是 Treap。因此以下内容全部是我自己想的。

这题之所以必须手写平衡树，关键在于，使用了平衡树的内部结构特点。Splay 可以通过旋转使得 [l,r] 全部排在一起。

一开始我受到这种方法的启发，尝试把 [l,r] 内的节点全部放在一棵子树上，然后把因此流离失所的节点重新安排新的父亲，然后再给 [l,r] 内节点打标记。想想就太麻烦了——因为孩子的缺失引起大量分类讨论，可能还不如写 Splay。

但是仔细一想，我们没有这个必要。或者说，把 [l,r] 内节点放一起的办法不适合于 WBLT。

WBLT 是线段树。

分离子树

想象一下，如果我们把 [l,r] 对应的子树全部拔出来，那么会产生 O(\log n) 棵子树和 O(\log n) 个缺口。我们直接把子树打上标记逆序插入这些缺口，不就好了吗。

接下来更新 sz。因为此时 sz 已经失效，所以再跑一遍分离子树的函数，并不能正确找到所有需要更新的非叶节点。因此我们需要记录每个点的父亲，然后通过第一个缺口和最后一个缺口的祖先找需要更新的节点。

更新 sz 的方法 1：端点的祖先

重新给这棵树“接骨”后，注意到我们需要重新修改 sz 的节点必然是第一个缺口的祖先和最后一个缺口祖先的并——如果有哪个点的两个孩子都被挖去了一部分，那么这个区间存在两个端点在这个点为根的子树内，而一个区间一共就两个端点，因此这样的点就只有一个，那就是两端点的 LCA。

更新 sz 的方法 2：使用 Vis 数组

不需要维护每个节点的父亲，只要在分离子树的时候记录经过的所有父节点即可。注意使用 Vis 数组的话，更新 sz 要倒着更新，也就是先更新后放入 Vis 的节点。

两种方法效率接近。之后写 WBLT 我可能更倾向于第二种。（

注意事项

还有要注意的点就是，多下放标记，不管是平衡前、输出前还是分裂前。

同样地，虽然每次插入新子树可能会很突然（可能把原来很小的子树换成很大的），但是平衡之后仍然保证每向下一层节点大小最多 \times 0.8，因此时间复杂度还是 1\log 的。

下面给出使用方法 1 的参考实现。因为一开始没想着要记录父亲数据，所以有些操作显得有些多余。

方法 1

方法 2

待填坑：可持久化平衡树

类似可持久化线段树，但是因为形态可能改变，可能有些细节。等我写一遍就知道了。