Weight Balance Leafy Tree

学习记录

介绍一个时间复杂度比非旋 Treap 更优，更稳定，不依赖随机数的算法，WBLT。

什么是 WBLT？

$\text{Weight Balanced Leafy Tree}$，是根据 $\text{Weight}$ 平衡的，信息记录在 $\text{Leafy Nodes}$ 上的树。讲人话就是一颗平衡线段树。大概结构就是这样：

graph TD
  A("1
w=3,sum=9") --> B("2
w=3,sum=9") --> C["3
w=1,sum=3"]
  B --> D["4
w=1,sum=2"]
  A --> E["5
w=1,sum=4"]
  1. 可以看到，其实 $w$ 就代表当前节点子树内有多少个叶子节点。
  2. 我们发现，WBLT 是满二叉树。
  3. WBLT 的 $\text{Non Leafy Node}$ 的左右子树都是 WBLT。
  4. 我们定义一个 WBLT 是 $\text{Balanced}$，当且仅当对于任意一个非叶子节点都有 $\dfrac{\min(w_l, w_r)}{w} \ge \alpha$。原论文指出 $\alpha \in [\dfrac{2}{11}, 1 - \dfrac{\sqrt 2}{2}]$ 可以保证时间复杂度是正确的，显然 $\alpha=\dfrac{1}{4}$ 是一个再好不过的选择了。

它支持什么？

  1. 区间操作（加、乘、懒标记等）
  2. 区间查询（和，矩阵乘积等）
  3. 区间复制
  4. 可持久化

时间复杂度：$\mathcal O(n\log n)$
空间复杂度：$\mathcal O(n)$

可以看出，几乎就是一个时间复杂度完全正确的，和 FHQ Treap 没什么两样的平衡树，甚至！比 FHQ Treap 还好写！！！

基础函数

  1. 1
    inline bool needBalance(int wl, int wr) { return wr * 3 < wl; }

    这个函数就是告诉你 $wl$ 比 $wr$ 重太多了，要减肥平衡了！

  2. 结构体定义（使用了语法糖）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    enum {L, R};
    struct Node {
        int ch[2], w, refCnt;
        LL sum, add; // tag
        
        Node& operator()(bool c);
        inline int& operator[](bool c) { return ch[c]; }
        
        inline void pushup() { if (w^1) sum = (*this)(L).sum + (*this)(R).sum, w = (*this)(L).w + (*this)(R).w; }
        inline void pull(LL x) { add += x; sum += x * w; }
        
        Node() : ch{}, w(), refCnt(), sum(), add() {}
        Node(int v) : ch{}, w(1), refCnt(1), sum(v), add() {}
        Node(int l, int r) : ch{l, r}, w(), refCnt(1), sum(), add() { pushup(); }
    } tr[N << 4];
    inline Node& Node::operator()(bool c) { return tr[ch[c]]; }

    这里，如果构造函数传 1 个参数，就是建一个 $\text{Leafy Node}$，否则就是根据给定的 $ls, rs$ 建 $\text{Non Leafy Node}$ 并且 pushup。

  3. 我们在进行平衡操作的时候，使用 merge 来维护平衡。

    • 如果有两颗树，左边树所有点下标（第一关键字）小于右边的，怎么合并成一颗？

    具体的，如果对于 $u$ 不平衡，我们现在假定了左右孩子的左右子树都是平衡的，那我们就可以通过如图所示的方式进行平衡：

        flowchart LR
   subgraph BEF[ ]
     direction TB
     A-->B([3])-->C((1)); B-->D([2])-->E((1)); B-->F((1));
     A-->G((1));
   end
   subgraph AFT[ ]
     direction TB
     a --> b([2]) --> c((1)); b-->d((1));
     a --> e([2]) --> f((1)); e --> g((1));
   end
   BEF --> AFT

    （这里的节点上的数字都代表 $w$）
    这只是一种例子，还有很多别的情况都大同小异，其实和 FHQ Treap 的合并没有什么两样。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    inline int merge(int l, int r) {
        if (!l || !r) return l | r;
        if (needBalance(tr[l].w, tr[r].w)) { // l too heavy
            auto [ll, lr] = cut(l);
            if (needBalance(tr[lr].w + tr[r].w, tr[ll].w)) {
                auto [lrl, lrr] = cut(lr);
                return alloc(alloc(ll, lrl), alloc(lrr, r));
            }
            return alloc(ll, alloc(lr, r));
        }
        if (needBalance(tr[r].w, tr[l].w)) { // r too heavy
            auto [rl, rr] = cut(r);
            if (needBalance(tr[l].w + tr[rl].w, tr[rr].w)) {
                auto [rll, rlr] = cut(rl);
                return alloc(alloc(l, rll), alloc(rlr, rr));
            }
            return alloc(alloc(l, rl), rr);
        }
        return alloc(l, r);
    }

    当然也有单双旋的版本：

    Single/Double Rotate 严格 $\mathcal O(1)$ 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    inline bool needDoubleRot(int u, bool x) { return tr[u](x).w * 2 < tr[u](!x).w; }
    inline void rotate(int &u, bool x) { // 将 u->x 旋转到 u
        auto [l, r] = cut(u);
        if (x) { // r heavier
            auto [rl, rr] = cut(r);
            u = alloc(alloc(l, rl), rr);
        } else {
            auto [ll, lr] = cut(l);
            u = alloc(ll, alloc(lr, r));
        }
    }
    inline void balance(int &u) {
        if (tr[u].w == 1) return;
        bool x = tr[u](R).w > tr[u](L).w; // 重儿子编号
        if (!needBalance(tr[u](x).w, tr[u](!x).w)) return;
        if (needDoubleRot(tr[u][x], x)) rotate(tr[u][x], !x); // 先一边倒，然后拉回来
        rotate(u, x);
    }
    inline int merge(int l, int r) {
        if (!l || !r) return l | r;
        if (needBalance(tr[l].w, tr[r].w)) { // l too heavy
            auto [ll, lr] = cut(l);
            int u = alloc(ll, alloc(lr, r));
            balance(u); return u;
        }
        if (needBalance(tr[r].w, tr[l].w)) { // r too heavy
            auto [rl, rr] = cut(r);
            int u = alloc(alloc(l, rl), rr);
            balance(u); return u;
        }
        return alloc(l, r);
    }

  4. 如果在区间复制的情景下：

    1
    2
    3
    4
    template<class... Args> inline int alloc(Args... args) {
        int u = bintop ? bin[bintop--] : ++top;
        tr[u] = Node(args...); return u;
    }

    使用 引用计数 保证空间复杂度线性。
    我们定义 $ref$ 表示引用的次数，那么 $ref=0$ 的时候就可以完全删除了。

    1
    2
    3
    4
    5
    6
    inline void recycle(int u) {
        if (u && --tr[u].refCnt == 0) {
            if (tr[u].w ^ 1) recycle(tr[u][L]), recycle(tr[u][R]);
            bin[++bintop] = u;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    inline void check(int &u) {
        if (tr[u].refCnt == 1) return;
        --tr[u].refCnt;
        if (tr[u].w != 1) ++tr[u](L).refCnt, ++tr[u](R).refCnt;
        tr[u = alloc(tr[u])].refCnt = 1;
    }

    inline void pushdown(int &u) {
        if (tr[u].w == 1 || !tr[u].add) return;
        check(u);
        if (tr[u][L]) check(tr[u][L]), tr[u](L).pull(tr[u].add);
        if (tr[u][R]) check(tr[u][R]), tr[u](R).pull(tr[u].add);
        tr[u].add = 0;
    }

    inline std::pair<int,int> cut(int& u) {
        if (tr[u].w == 1) return {0,0};
        pushdown(u);
        ++tr[u](L).refCnt, ++tr[u](R).refCnt;
        std::pair<int,int> ret(tr[u][L], tr[u][R]);
        recycle(u);
        u = 0; // u 没啦！再用，你想 use-after-free 喵？
        return ret;
    }

    这里我们秉持着可持久化原则，如果我被人用了，那我修改节点信息肯定不能直接修改，要另起炉灶。但是我的两个小弟仍然归我，所以他们都又多了一个个师傅。

  5. 分割平衡树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    inline std::pair<int,int> split(int u, int ord) {
        if (!ord) return {0, u};
        if (ord == tr[u].w) return {u, 0};
        auto [l, r] = cut(u);
        if (ord <= tr[l].w) {
            auto [ll, lr] = split(l, ord);
            return {ll, merge(lr, r)};
        }
        auto [rl, rr] = split(r, ord - tr[l].w);
        return {merge(l, rl), rr};
    }

    （将 $u$ 这颗树的前 $ord$ 个节点分割出来，返回前 $ord$ 个节点的树的根指针 和 其余节点的树的根指针）

实用函数

  1. 建树

    1
    2
    3
    4
    5
    int build(int l, int r) {
        if (l == r) return alloc(a[l]);
        int mid = l + r >> 1;
        return alloc(build(l, mid), build(mid + 1, r));
    }

    （将 $a[l] \dots a[r]$ 建成一颗树，返回根节点指针）

  2. 区间加

    1
    2
    3
    4
    5
    6
    7
    #define fetch(L, R) ++L, ++R, ++R; auto [tmp, r] = split(root, R); auto [l, u] = split(tmp, L)

    inline void plus(int L, int R, int d) {
        fetch(L, R);
        tr[u].pull(d);
        root = merge(merge(l, u), r);
    }

  3. 区间复制

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    inline void copy(int dL, int dR, int sL, int sR) {
        int src; { // Copy src
            fetch(sL, sR);
            ++tr[src = u].refCnt;
            root = merge(merge(l, u), r);
        }
        fetch(dL, dR);
        root = merge(merge(l, src), r);
        recycle(u);
    }

  4. 提取原数组 $\mathcal O(n)$

    1
    2
    3
    4
    5
    6
    7
    8
    inline void extract(std::vector<int> &vec, int &u = root) {
        if (tr[u].w == 1) vec.push_back(tr[u].sum);
        else {
            pushdown(u);
            extract(vec, tr[u][L]);
            extract(vec, tr[u][R]);
        }
    }