#include<codesonic>

#include<codesonic>

using namespace FST;

WBLT 实用入门和讲解

posted on 2019-01-20 17:11:03 | under 未分类 |

update on 2019/3/17

我原来似乎写过双旋的WBLT,但是因为发现删掉在模板题会更快就删掉了,给出代码(只有maintain函数变了)

=========================分割线===============================

WBLT 全称Weight Balanced Leafy Tree.是一种常数较小,代码较简单的平衡树实现方式。

在看本文之前,推荐您先学习treap等平衡树 这篇文章对于有平衡树基础的人较为友好

定义和引入

WBLT是二叉搜索树的一种。不同的是,他同时是一个大根堆(也可以是小根堆),每个非叶节点都有两个儿子,且每个节点的权值与其右儿子的权值相同,且左儿子的权值小于右儿子的权值,左子树的所有节点的权值小于右子树任意节点的权值。

也就是说他大概长这样:

这种设计有一个明显的缺点 就是如果要储存n个数据,普通的平衡树需要开n个节点,而WBLT需要开2n-1个

也就是说 储存上图的数据的treap长这样:

那么 相比之下它有什么好处呢?

旋转

WBLT= Weight Balanced Tree(加权平衡树) + Leafy,其中Leafy已经在_定义和引入_中体现了,平衡是指一个节点的左子树和右子树大小近似相同,这样在查询/修改的时候才能做到近似log,旋转便是维护平衡的方便手段

因为其结构特殊 不需要像treap一样引入一个rand,只要旋转就可以维护其平衡。

先给出旋转的代码

inline void merge(int l,int r){
    size[++cnt]=size[l]+size[r];
    val[cnt]=val[r];
    ls[cnt]=l,rs[cnt]=r;
}

inline void rotate(int cur,bool flag){
    if(flag){
        merge(ls[cur],ls[rs[cur]]);
        ls[cur]=cnt;
        rs[cur]=rs[rs[cur]];
    }//左旋
    else{
        merge(rs[ls[cur]],rs[cur]);
        rs[cur]=cnt;
        ls[cur]=ls[ls[cur]];
    }//右旋
}

再给出图例(节点上的数字为编号,数字颜色为红色则为新节点): 可以发现,旋转后的WBLT仍然保持原来的性质。而且明显偏重的左子树转到了右边,左右子树相对平衡了。

查询排名为x的数

我们记录每个节点的size,这个size不是子树的大小,而是子树储存的有效信息的大小。

因为有性质储存n个数据要开2n-1个节点,所以如果一个子树的大小为 $2x-1$ ,那它储存的数据量就有 $x$ 个。

接下来的操作就简单了,令find(cur,x)为寻找cur所在的子树下排名为x的数,那么当x比左子树的size小

$find(cur,x)=find(lson_{cur},x)$

当x比左子树的size大

$find(cur,x)=find(rson_{cur},x-size_{lson_{cur}})$

如果相等,那显然

$find(cur,x)=val_{cur}$

因为当前要找的是第x大,那我无需遍历下面,这点也与treap不同

int find(int cur,int x){
    if(size[cur]==x)
        return val[cur];
    if(x>size[ls[cur]])
        return find(rs[cur],x-size[ls[cur]]);
    return find(ls[cur],x);
}

查询x的排名

同理,设rnk(cur,x)为寻找cur子树下x的排名

当x小于cur的左儿子的权值

$rnk(cur,x)=rnk(lson_{cur},x)$

否则

$rnk(cur,x)=size_{lson_{cur}}+rnk(rson_{cur},x)$

int rnk(int cur,int x){
    if(size[cur]==1)
        return 1;
    if(x>val[ls[cur]])
        return rnk(rs[cur],x)+size[ls[cur]];
    return rnk(ls[cur],x);
}

插入

WBLT其他的操作都与treap类似,在每一步时:

根据要添加的权值和当前搜索到的节点选择左右子树进行递归(如果比左儿子的权值大就去右子树,否则去左子树)

递归到最后一步到一个叶子节点时,根据其权值大小建立新节点,确定是该节点的左儿子还是右儿子

建立它的兄弟节点。

向上pushup(类似于线段树,儿子会影响父亲,这点于与treap不同)。

void insert(int cur,int x){
    if(size[cur]==1){
        newnode(ls[cur],minn(x,val[cur]));
        newnode(rs[cur],maxx(x,val[cur]));
        pushup(cur);
        return ;
    }
    insert(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

删除

在每一步时:

根据要删除权值和当前搜索到的节点选择左右子树进行递归(如果比左儿子的权值大就去右子树,否则去左子树)

递归到最后一步到一个叶子节点时,判断该节点是不是要删除的,如果不是则选择其兄弟节点,进行删除,将两个节点中保留的与其父亲节点进行替换

向上pushup。

void erase(int cur,int x){
    if(size[cur]==1){
        cur= ls[fa]==cur?rs[fa]:ls[fa];
        copynode(fa,cur);
        return ;
    }
    fa=cur;
    erase(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

P3369

等等 旋转呢?

我们在上文所有的操作中,似乎没有使用旋转,那旋转放在哪呢?

我们将其放在树的结构有改变的地方,也就是插入 删除这些操作中,每当一个子树过大,就进行相应的旋转,在插入和删除操作中加入以下函数即可

const int ratio=5;

inline void maintain(int cur){
    if(size[ls[cur]]>size[rs[cur]]*ratio)
        rotate(cur,0);
    else if(size[rs[cur]]>size[ls[cur]]*ratio)
        rotate(cur,1);
}

那么普通平衡树的代码如下

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int maxn=400010;
const int ratio=5;

int n,cnt,fa,root;
int size[maxn],ls[maxn],rs[maxn],val[maxn];

inline void newnode(int &cur,int v){
    cur=++cnt;
    size[cur]=1;
    val[cur]=v;
}

inline void copynode(int x,int y){
    size[x]=size[y];
    ls[x]=ls[y],rs[x]=rs[y];
    val[x]=val[y];
}

inline void merge(int l,int r){
    size[++cnt]=size[l]+size[r];
    val[cnt]=val[r];
    ls[cnt]=l,rs[cnt]=r;
}

inline void rotate(int cur,bool flag){
    if(flag){
        merge(ls[cur],ls[rs[cur]]);
        ls[cur]=cnt;
        rs[cur]=rs[rs[cur]];
    }
    else{
        merge(rs[ls[cur]],rs[cur]);
        rs[cur]=cnt;
        ls[cur]=ls[ls[cur]];
    }
}

inline void maintain(int cur){
    if(size[ls[cur]]>size[rs[cur]]*ratio)
        rotate(cur,0);
    else if(size[rs[cur]]>size[ls[cur]]*ratio)
        rotate(cur,1);
}

inline void pushup(int cur){
    if(!size[ls[cur]])return ;
    size[cur]=size[ls[cur]]+size[rs[cur]];
    val[cur]=val[rs[cur]];
}

inline int minn(int a,int b){
    return a<b?a:b;
}
inline int maxx(int a,int b){
    return a>b?a:b;
}

inline void insert(int cur,int x){
    if(size[cur]==1){
        newnode(ls[cur],minn(x,val[cur]));
        newnode(rs[cur],maxx(x,val[cur]));
        pushup(cur);
        return ;
    }
    maintain(cur);
    insert(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

inline void erase(int cur,int x){
    if(size[cur]==1){
        cur= ls[fa]==cur?rs[fa]:ls[fa];
        copynode(fa,cur);
        return ;
    }
    maintain(cur);
    fa=cur;
    erase(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

inline int find(int cur,int x){
    if(size[cur]==x)
        return val[cur];
    maintain(cur);
    if(x>size[ls[cur]])
        return find(rs[cur],x-size[ls[cur]]);
    return find(ls[cur],x);
}

inline int rnk(int cur,int x){
    if(size[cur]==1)
        return 1;
    maintain(cur);
    if(x>val[ls[cur]])
        return rnk(rs[cur],x)+size[ls[cur]];
    return rnk(ls[cur],x);
}

int main(){
    scanf("%d",&n);
    newnode(root,(1<<30));
    while(n--){
        int s,x;
        scanf("%d%d",&s,&x);
        if(s==1)insert(root,x);
        if(s==2)erase(root,x);
        if(s==3)printf("%d\n",rnk(root,x));
        if(s==4)printf("%d\n",find(root,x));
        if(s==5)printf("%d\n",find(root,rnk(root,x)-1));
        if(s==6)printf("%d\n",find(root,rnk(root,x+1)));
    }
    return 0;
}

以下是评测记录

上面的是treap,下面的是WBLT(O2,scanf读入)

我们发现,WBLT只比treap慢一点点,所以WBLT和treap几乎是一样块的~

例题

P1503 鬼子进村

平衡树部分是个裸题,其他倒还得想想

先把0和n+1插入,作为边界

摧毁节点就插入该点

删除上一个就维护个栈,删除栈顶即可

询问操作就查找前驱和后继,一减就行了,记得特判是否已经被摧毁(记个vis数组即可)

代码

P2596 [ZJOI2006]书架

平衡树部分还是个裸题

定义优先级越小,那本书就放越上面

设 $a_i$ 为编号为 $i$ 的书本的优先级, $mapp_i$ 为优先级为i的节点编号。

Top S:将优先级变为最小再插入

Bottom S:将优先级变为最大再插入

Insert S T:找到对应两本书 交换优先级

Ask S:查询优先级排名

Query S:查询第k小的优先级对应的编号

代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>

using namespace std;

const int maxn=400010;
const int ratio=5;

inline int read(){
    register int num=0,flag=1;char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') break;
    if(ch=='-') flag=-1;
    else num=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') num=num*10+ch-'0';
    return num*flag; 
}
void out(int x){
    if(x>=10) out(x/10);
    putchar(x%10+'0');
}

int n,m,cnt,fa,root;
int size[maxn],ls[maxn],rs[maxn],val[maxn],a[maxn];
int mapp[maxn];

/*此处有省略,平衡树部分请参照上文*/

char opt[20];
int k,l,r,i;

int main() {
    n=read();
    m=read();
    newnode(root,(1<<30));
    l=233333,r=n+233333;
    for(i=1; i<=n; i++) {
        int qaq;
        qaq=read();
        insert(root,i+233333);
        a[qaq]=i+233333;
        mapp[i+233333]=qaq;
    }
    while(m--) {
        scanf("%s",opt);
        if(opt[0]=='Q') {
            k=read();
            out(mapp[find(root,k)]);
            putchar('\n');
        } else if(opt[0]=='A') {
            k=read();
            out(rnk(root,a[k])-1);
            putchar('\n');
        } else if(opt[0]=='T') {
            k=read();
            erase(root,a[k]);
            insert(root,--l);
            a[k]=l;
            mapp[l]=k;
        } else if(opt[0]=='B') {
            k=read();
            erase(root,a[k]);
            insert(root,++r);
            a[k]=r;
            mapp[r]=k;
        } else if(opt[0]=='I') {
            register int s=read(),t=read();
            if(t==1) {
                int rnk2=rnk(root,a[s]),rnk1=rnk2+1;
                int s2=find(root,rnk1);
                s2=mapp[s2];
                erase(root,a[s]);
                erase(root,a[s2]);
                swap(a[s],a[s2]);
                mapp[a[s]]=s;
                mapp[a[s2]]=s2;
                insert(root,a[s]);
                insert(root,a[s2]);
            } else if(t==-1) {
                int rnk2=rnk(root,a[s]),rnk1=rnk2-1;
                int s2=find(root,rnk1);
                s2=mapp[s2];
                erase(root,a[s]);
                erase(root,a[s2]);
                swap(a[s],a[s2]);
                mapp[a[s]]=s;
                mapp[a[s2]]=s2;
                insert(root,a[s]);
                insert(root,a[s2]);
            }
        }
    }
    return 0;
}

结果这个吊打了splay ,和fhq-treap差不了多少

而且似乎比同种思路的treap快了300ms左右

总结

WBLT有着显著的优缺点

优点是快(nlogn 常数较小) 好记 码量小 且能实现很多功能(基本包括treap的所有操作)

缺点是空间大尽管可以用垃圾回收补偿,但是仍然需要两倍的空间

备注:这个是单旋,没法证复杂度但是难以卡掉。2018集训队论文里那个是双旋,是复杂度正确的。

最后用一张图结束本文吧

(发完引战言论就跑