WBLT 小记

piggy123 · 2024-02-28 07:31:28 · 个人记录

暨 WC 李欣隆《浅谈持久化数据结构》及集训队论文 2018 王思齐《Leafy Tree 及其实现的加权平衡树》阅读笔记。

WBLT（Weight Balanced leafy tree 加权平衡线段树）是一种轻量级的平衡树。

WBLT 和线段树维护方法相似，实现简单，容易理解。并且通过分裂、合并等操作，可以支持和 FHQ Treap，Splay 一样区间反转等的许多功能。

缺点在于空间消耗较大，是 Treap 等一般平衡树的两倍。一般来说，可以通过垃圾回收等方法将空间限制在一个合理范围内，但这个缺点在可持久化时尤其明显，因为不能垃圾回收。

插入、删除和查询 K 小值

每个节点保存该子树内的最大值与左右孩子，每插入一个值在树上二分找到插入点，将这个节点从父节点上摘下来，新建一个节点，左右节点分别为摘下来的节点与新加入的节点，再将这个节点连接到摘下节点的父节点上。

删除同理，注意 WBLT 要求非叶结点都有两个儿子，所以删除一个叶子时需要将他的父亲节点替换为他的兄弟节点。

K 小值可以和线段树一样查询，非常方便。

调整平衡

定义一个点的不平衡度为他的左右子树中较小的那个比上这个点的子树大小。设立阈值 \alpha，若一个点的不平衡度小于 \alpha，则这个节点不能维持平衡，就需要进行旋转操作以维持平衡。

下面不加证明地给出旋转方法，以右旋为例，左旋对称：

当左子树的左子树大小比上左子树大小小于 \frac{1-2\alpha}{1-\alpha} 时，将左子树进行一次左旋，否则不动（这次操作称为“双旋”）。

接着将左子树的左子树作为原节点的左子树，将左子树的右子树与原右子树直接合并作为原节点的右子树（这里的“直接合并”指新建一个节点，以这两个子树为左右子树，显然这是 \Theta(1) 的，下同）。（这次操作称为“单旋”）

一般取 \alpha\sim1-\frac{\sqrt{2}}{2}，注意需要保证 \alpha\lt \frac{1}{4} 才能保证正确性（这是显然的）。

下面是可以通过 P6136 普通平衡树（加强版）的代码：

#include <bits/stdc++.h>
#define ll int
#define ull unsigned long long
using namespace std;

struct node {
    ll vl,ls,rs,sz;
} tree[4000005];
ll tot=1,sz=0;

ll nwnd(ll v,ll ls,ll rs,ll sz) {
    ++tot;
    tree[tot].ls=ls;
    tree[tot].rs=rs;
    tree[tot].vl=v;
    tree[tot].sz=sz;
    return tot;
}

void pushup(ll root) {
    if (!tree[root].ls&&!tree[root].rs) {
        tree[root].sz=1;
        return;
    }
    tree[root].sz=tree[tree[root].ls].sz+tree[tree[root].rs].sz;
    tree[root].vl=max(tree[tree[root].ls].vl,tree[tree[root].rs].vl);
}

ll merge(ll rt1,ll rt2) {
    return nwnd(max(tree[rt1].vl,tree[rt2].vl),rt1,rt2,tree[rt1].sz+tree[rt2].sz);
}

void rotate(ll root,ll tp) {

    if (tp==0) {
        // left
        if (tree[tree[root].rs].sz<=1)return;
        tree[root].ls=merge(tree[root].ls,tree[tree[root].rs].ls);
        tree[root].rs=tree[tree[root].rs].rs;
    } else {
        // right
        if (tree[tree[root].ls].sz<=1)return;
        tree[root].rs=merge(tree[tree[root].ls].rs,tree[root].rs);
        tree[root].ls=tree[tree[root].ls].ls;
    }
}

const double a=0.27;
void maintain(ll root) {
    if (tree[tree[root].ls].sz<a*tree[root].sz) {
        if (tree[tree[tree[root].rs].rs].sz*1.0/tree[tree[tree[root].rs].ls].sz<=(1-2*a)/(1-a))rotate(tree[root].rs,1);
        rotate(root,0);
    } else if (tree[tree[root].rs].sz<a*tree[root].sz) {
        if (tree[tree[tree[root].ls].ls].sz*1.0/tree[tree[tree[root].ls].rs].sz<=(1-2*a)/(1-a))rotate(tree[root].ls,0);

        rotate(root,1);
    }

}

void insert(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        tree[root].ls=nwnd(min(tree[root].vl,v),0,0,1);
        tree[root].rs=nwnd(max(tree[root].vl,v),0,0,1);
        tree[root].vl=max(tree[root].vl,v);
        pushup(root);
        maintain(root);
        return;
    }
    if (v<=tree[tree[root].ls].vl) {
        insert(tree[root].ls,v);
    } else {
        insert(tree[root].rs,v);
    }
    pushup(root);
    maintain(root);
}

void del(ll root,ll v,ll fa) {
    if (!tree[root].ls&&!tree[root].rs) {
        if (tree[root].vl!=v)return;
        if (tree[fa].ls==root) {
            tree[fa]=tree[tree[fa].rs];
        } else {
            tree[fa]=tree[tree[fa].ls];
        }
        return;
    }
    if (v<=tree[tree[root].ls].vl) {
        del(tree[root].ls,v,root);
    } else {
        del(tree[root].rs,v,root);
    }
    pushup(root);
    maintain(root);
}

ll getplc(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        return tree[root].vl;
    }
    if (tree[tree[root].ls].sz>=v) {
        return getplc(tree[root].ls,v);
    } else {
        return getplc(tree[root].rs,v-tree[tree[root].ls].sz);
    }
}

ll getrk(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        return tree[root].vl<v;
    }
    if (v<=tree[tree[root].ls].vl) {
        return getrk(tree[root].ls,v);
    } else {
        return getrk(tree[root].rs,v)+tree[tree[root].ls].sz;
    }
}

ll getrk2(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        return tree[root].vl<=v;
    }
    if (v<tree[tree[root].ls].vl) {
        return getrk2(tree[root].ls,v);
    } else {
        return getrk2(tree[root].rs,v)+tree[tree[root].ls].sz;
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    for (ll i=1; i<=n; i++) {
        ll x;
        cin >> x;
        if (sz==0) {
            tree[1].ls=tree[1].rs=0;
            tree[1].vl=x;
            tree[1].sz=1;
        } else {
            insert(1,x);
        }
        sz++;
    }
    ll lst=0,xo=0;
    for (ll i=1; i<=m; i++) {
        ll opt,x;
        cin >> opt >> x;
        x^=lst;
        if (opt==1) {
            if (sz==0) {
                tree[1].ls=tree[1].rs=0;
                tree[1].vl=x;
                tree[1].sz=1;
            } else {
                insert(1,x);
            }
            sz++;
        } else if (opt==2) {
            del(1,x,0);
            sz--;
        } else if (opt==3) {
            if (sz==0)
            xo^=(lst=1);
            else
            xo^=(lst=getrk(1,x)+1);
        } else if (opt==4) {
            xo^=(lst=getplc(1,x));
        } else if (opt==5) {
            xo^=(lst=getplc(1,getrk(1,x)));
        } else {
            xo^=(lst=getplc(1,getrk2(1,x)+1));
        }
    }
    cout<< xo;
    return 0;
}

合并与分裂

下面不加证明地给出合并方法，以左子树大小较大为例，右子树较大对称：

如果两个子树直接合并可以维持平衡，则直接合并；否则，如果将左子树的左子树作为新的左子树可以维持平衡，则递归合并左子树的右子树与右子树；否则，将左子树左旋，递归合并左子树的右子树与右子树。

分裂方法是容易的，直接二分定位并调用上面的合并即可。

那么效仿 Splay 打标记并下传即可，实际上这和线段树非常相像，只是多了一个调整平衡的 miantain 函数罢了。

合并和分裂操作的复杂度为 \Theta(\log_{sz_a}-\log_{sz_b})。

注意：由于分裂和合并会调用非常多的无用节点，如果不进行垃圾回收那么空间会退化为 \Theta(n\log n)，不可接受，所以必须垃圾回收。

下面是 P3391 文艺平衡树的代码：

#include <bits/stdc++.h>
#define ll int
#define ull unsigned long long
using namespace std;

struct node {
    ll vl,ls,rs,sz,revtag;
} tree[4000005];
ll tot=1,rt=1,sz=0,A[1000005];
queue<ll> pool;

inline void del(ll node) {
    pool.push(node);
}

inline ll nwnd(ll v,ll ls,ll rs,ll sz) {
    ll nw=0;
    if (pool.empty())
        nw=++tot;
    else
        nw=pool.front(),pool.pop();
    tree[nw].ls=ls;
    tree[nw].rs=rs;
    tree[nw].vl=v;
    tree[nw].sz=sz;
    tree[nw].revtag=0;
    return nw;
}

inline void pushup(ll root) {
    if (!tree[root].ls&&!tree[root].rs) {
        tree[root].sz=1;
        return;
    }
    tree[root].sz=tree[tree[root].ls].sz+tree[tree[root].rs].sz;
    tree[root].vl=max(tree[tree[root].ls].vl,tree[tree[root].rs].vl);
}

inline void pushdown(ll root) {
    if (tree[root].revtag) {
        tree[tree[root].ls].revtag^=1;
        tree[tree[root].rs].revtag^=1;
        swap(tree[tree[root].ls].ls,tree[tree[root].ls].rs);
        swap(tree[tree[root].rs].ls,tree[tree[root].rs].rs);
        tree[root].revtag=0;
    }
}

inline ll merge1(ll rt1,ll rt2) {
    return nwnd(max(tree[rt1].vl,tree[rt2].vl),rt1,rt2,tree[rt1].sz+tree[rt2].sz);
}

inline void rotate(ll root,ll tp) {
    pushdown(root);
    if (tp==0) {
        // left
        if (tree[tree[root].rs].sz<=1)return;
        pushdown(tree[root].rs);
        ll tmp=tree[root].rs;
        tree[root].ls=merge1(tree[root].ls,tree[tree[root].rs].ls);
        tree[root].rs=tree[tree[root].rs].rs;
        del(tmp);
    } else {
        // right
        if (tree[tree[root].ls].sz<=1)return;
        pushdown(tree[root].ls);
        ll tmp=tree[root].ls;
        tree[root].rs=merge1(tree[tree[root].ls].rs,tree[root].rs);
        tree[root].ls=tree[tree[root].ls].ls;
        del(tmp);
    }
}

const double a=0.27;
inline void maintain(ll root) {
    if (tree[tree[root].ls].sz<a*tree[root].sz) {
        if (tree[tree[tree[root].rs].rs].sz*1.0/tree[tree[tree[root].rs].ls].sz<=(1-2*a)/(1-a))rotate(tree[root].rs,1);
        rotate(root,0);
    } else if (tree[tree[root].rs].sz<a*tree[root].sz) {
        if (tree[tree[tree[root].ls].ls].sz*1.0/tree[tree[tree[root].ls].rs].sz<=(1-2*a)/(1-a))rotate(tree[root].ls,0);
        rotate(root,1);
    }

}

void insert(ll root,ll v) {
    if (sz==0) {
        tree[root].vl=v;
        tree[root].ls=tree[root].rs=0;
        return;
    }
    if (!tree[root].ls&&!tree[root].rs) {
        tree[root].ls=nwnd(min(tree[root].vl,v),0,0,1);
        tree[root].rs=nwnd(max(tree[root].vl,v),0,0,1);
        tree[root].vl=max(tree[root].vl,v);
        pushup(root);
        maintain(root);
        return;
    }
    pushdown(root);
    if (v<=tree[tree[root].ls].vl) {
        insert(tree[root].ls,v);
    } else {
        insert(tree[root].rs,v);
    }
    pushup(root);
    maintain(root);
}

ll merge(ll rt1,ll rt2) {
    if (!rt1||!rt2)return rt1?rt1:rt2;
    if (min(tree[rt1].sz,tree[rt2].sz)>=a*(tree[rt1].sz+tree[rt2].sz)) {
        ll nw=nwnd(max(tree[rt1].vl,tree[rt2].vl),rt1,rt2,tree[rt1].sz+tree[rt2].sz);
        return nw;
    }
    pushdown(rt1);
    pushdown(rt2);
    if(tree[rt1].sz>tree[rt2].sz) {
        if ((tree[tree[rt1].rs].sz+tree[rt2].sz)>=a*(tree[rt1].sz+tree[rt2].sz)) {
            ll tmp=merge1(tree[rt1].ls,merge(tree[rt1].rs,rt2));
            del(rt1);
            return tmp;
        }
        rotate(rt1,1);
        ll tmp=merge(tree[rt1].ls,merge(tree[rt1].rs,rt2));
        del(rt1);
        return tmp;
    } else {
        if ((tree[tree[rt2].ls].sz+tree[rt1].sz)>=a*(tree[rt1].sz+tree[rt2].sz)) {
            ll tmp=merge1(merge(rt1,tree[rt2].ls),tree[rt2].rs);
            del(rt2);
            return tmp;
        }
        rotate(rt2,0);
        ll tmp=merge(merge(rt1,tree[rt2].ls),tree[rt2].rs);
        del(rt2);
        return tmp;
    }
}

void split(ll root,ll v,ll &rt1,ll &rt2) {

    if (!tree[root].ls&&!tree[root].rs) {
        if (v==0)rt1=0,rt2=root;
        else rt1=root,rt2=0;
        return;
    }
    pushdown(root);
    if (v<=tree[tree[root].ls].sz) {
        split(tree[root].ls,v,rt1,rt2);
        rt2=merge(rt2,tree[root].rs);
        del(root);
    } else {
        split(tree[root].rs,v-tree[tree[root].ls].sz,rt1,rt2);
        rt1=merge(tree[root].ls,rt1);
        del(root);
    }
}

void dfs(ll root) {
    if (!tree[root].ls&&!tree[root].rs) {
        cout<<tree[root].vl<<" ";
        return;
    }
    pushdown(root);
    dfs(tree[root].ls);
    dfs(tree[root].rs);
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    for (ll i=1; i<=n; i++) {
        A[i]=i;
        insert(1,i);
        sz++;
    }
    for (ll i=1; i<=m; i++) {
        ll l,r;
        cin >> l >> r;
        ll rt1=0,rt2=0,rt3=0,rt4=0;
        split(rt,l-1,rt1,rt2);
        split(rt2,r-l+1,rt3,rt4);
        tree[rt3].revtag^=1;
        swap(tree[rt3].ls,tree[rt3].rs);
        rt=merge(merge(rt1,rt3),rt4);
    }
    dfs(rt);
    return 0;
}

持久化

注意到 WBLT 是父亲指向儿子，儿子不储存父亲的优秀结构，所以可以直接使用路径复制的方法进行可持久化，即将修改的节点全部复制一遍即可。注意旋转时需要新开很多无用节点并且大多不能垃圾回收，所以空间要开大，略大于 \Theta((n+m)\log n)。

下面是 P3835 可持久化平衡树的代码：

#include <bits/stdc++.h>
#define ll int
#define ull unsigned long long
using namespace std;

struct node {
    ll vl,ls,rs,sz;
} tree[4000005];
ll tot=1,sz=0,rt[500005];
queue<ll> pool;

inline void del(ll node){
    pool.push(node);
}

inline ll nwnd(ll v,ll ls,ll rs,ll sz) {
    ll nw=0;
    if (!pool.empty())
    nw=pool.front();
    else
    nw=++tot;
    tree[nw].ls=ls;
    tree[nw].rs=rs;
    tree[nw].vl=v;
    tree[nw].sz=sz;
    return nw;
}

inline void pushup(ll root) {
    if (!tree[root].ls&&!tree[root].rs) {
        tree[root].sz=1;
        return;
    }
    tree[root].sz=tree[tree[root].ls].sz+tree[tree[root].rs].sz;
    tree[root].vl=max(tree[tree[root].ls].vl,tree[tree[root].rs].vl);
}

inline ll merge(ll rt1,ll rt2) {
    return nwnd(max(tree[rt1].vl,tree[rt2].vl),rt1,rt2,tree[rt1].sz+tree[rt2].sz);
}

ll rotate(ll root,ll tp) {
    ll nw=nwnd(tree[root].vl,0,0,tree[root].sz);
    if (tp==0) {
        // left
        if (tree[tree[root].rs].sz<=1)return root;
        tree[nw].ls=merge(tree[root].ls,tree[tree[root].rs].ls);
        tree[nw].rs=tree[tree[root].rs].rs;
    } else {
        // right
        if (tree[tree[root].ls].sz<=1)return root;
        tree[nw].rs=merge(tree[tree[root].ls].rs,tree[root].rs);
        tree[nw].ls=tree[tree[root].ls].ls;
    }
    return nw;
}

const double a=0.2928;
void maintain(ll root) {
    ll nw=0;
    if (tree[tree[root].ls].sz<a*tree[root].sz) {
        if (tree[tree[tree[root].rs].rs].sz*1.0/tree[tree[tree[root].rs].ls].sz<=(1-2*a)/(1-a))tree[root].rs=rotate(tree[root].rs,1);
        nw=rotate(root,0);
    } else if (tree[tree[root].rs].sz<a*tree[root].sz) {
        if (tree[tree[tree[root].ls].ls].sz*1.0/tree[tree[tree[root].ls].rs].sz<=(1-2*a)/(1-a))tree[root].ls=rotate(tree[root].ls,0);
        nw=rotate(root,1);
    }
    if (nw)
    tree[root]=tree[nw];
}

void insert(ll &root,ll od,ll v) {
    root=nwnd(max(v,tree[od].vl),tree[od].ls,tree[od].rs,tree[od].sz+1);
    if (!tree[root].ls&&!tree[root].rs) {
        tree[root].ls=nwnd(min(tree[root].vl,v),0,0,1);
        tree[root].rs=nwnd(max(tree[root].vl,v),0,0,1);
        tree[root].vl=max(tree[root].vl,v);
        pushup(root);
        return;
    }
    if (v<=tree[tree[od].ls].vl) {
        insert(tree[root].ls,tree[od].ls,v);
    } else {
        insert(tree[root].rs,tree[od].rs,v);
    }
    pushup(root);
    maintain(root);
}

void del(ll &root,ll od,ll v,ll fa) {
    root=nwnd(tree[od].vl,tree[od].ls,tree[od].rs,tree[od].sz-1);
    if (!tree[root].ls&&!tree[root].rs) {
        if (tree[root].vl!=v){
            pushup(root);
            return;
        }
        if (tree[fa].ls==root) {
            tree[fa]=tree[tree[fa].rs];
        } else {
            tree[fa]=tree[tree[fa].ls];
        }
        pushup(root);
        return;
    }
    if (v<=tree[tree[root].ls].vl) {
        del(tree[root].ls,tree[od].ls,v,root);
    } else {
        del(tree[root].rs,tree[od].rs,v,root);
    }
    pushup(root);
    maintain(root);
}

ll getplc(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        return tree[root].vl;
    }
    if (tree[tree[root].ls].sz>=v) {
        return getplc(tree[root].ls,v);
    } else {
        return getplc(tree[root].rs,v-tree[tree[root].ls].sz);
    }
}

ll getrk(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        return tree[root].vl<v;
    }
    if (v<=tree[tree[root].ls].vl) {
        return getrk(tree[root].ls,v);
    } else {
        return getrk(tree[root].rs,v)+tree[tree[root].ls].sz;
    }
}

ll getrk2(ll root,ll v) {
    if (!tree[root].ls&&!tree[root].rs) {
        return tree[root].vl<=v;
    }
    if (v<=tree[tree[root].ls].vl) {
        return getrk2(tree[root].ls,v);
    } else {
        return getrk2(tree[root].rs,v)+tree[tree[root].ls].sz;
    }
}

void dfs(ll root) {
    if (!tree[root].ls&&!tree[root].rs) {
        cout<<tree[root].vl<<" ";
        return;
    }
    dfs(tree[root].ls);
    dfs(tree[root].rs);
}

const ll inf=2147483647;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll lst=0,xo=0;
    rt[0]=1;
    tree[1].sz=2;
    tree[1].ls=2;
    tree[1].rs=3;
    tree[1].vl=inf;
    tree[2].sz=1;
    tree[2].vl=-inf;
    tree[3].sz=1;
    tree[3].vl=inf;
    tot=3;
    ll totz=0;
    for (ll i=1; i<=n; i++) {
        ll v,opt,x;
        cin >>v>> opt >> x;
        if (opt==1) {
            insert(rt[i],rt[v],x);
        } else if (opt==2) {
            del(rt[i],rt[v],x,0);
        } else if (opt==3) {
            cout<< getrk(rt[i]=rt[v],x)<<"\n";
        } else if (opt==4) {
            cout<<getplc(rt[i]=rt[v],x+1)<<"\n";
        } else if (opt==5) {
            cout<< getplc(rt[i]=rt[v],getrk(rt[v],x))<<"\n";
        } else {
            cout<< getplc(rt[i]=rt[v],getrk2(rt[v],x)+1)<<"\n";
        }
    }

    return 0;
}

一些特殊应用

lxl 在讲课中提到，由于 WBLT 合并的优秀性质，在对于一些特殊的 WBLT 的合并是优秀于 \Theta(\log n) 的。比如 P8263 区间复制 K 次操作，用 WBLT 进行倍增合并可以做到 \Theta(1) 合并（经过一些分析可以得到合并答案也是均摊 \Theta(1)），则复杂度变为 \Theta(n\log n)，优于 Treap。

代码还没写。

一些一般应用

CF702E T-shirts

容易用平衡树维护操作，但是注意到合并时集合有交，但是有交的部分合并一次必然折半，所以暴力插入即可，复杂度两个 \log。代码见提交记录。

我们也可以直接考虑可持久化，用路径复制的方法，每次复制一段区间再给一个区间打标记再合并，复杂度一个 \log 还可以做到在线。代码很难写，不打算写了。