WBLT 实用入门和讲解

update on 2019/3/17 我原来似乎写过双旋的WBLT，但是因为发现删掉在模板题会更快就删掉了，给出[代码](https://www.luogu.org/paste/x63xel1o)（只有maintain函数变了） =========================分割线=============================== WBLT 全称Weight Balanced Leafy Tree.是一种常数较小，代码较简单的平衡树实现方式。 在看本文之前，推荐您先学习treap等平衡树 这篇文章对于有平衡树基础的人较为友好 ## 定义和引入 WBLT是二叉搜索树的一种。不同的是，他同时是一个大根堆（也可以是小根堆），每个非叶节点都有两个儿子，且每个节点的权值与其右儿子的权值相同，且左儿子的权值小于右儿子的权值，左子树的所有节点的权值小于右子树任意节点的权值。 也就是说他大概长这样：  这种设计有一个明显的缺点 就是如果要储存n个数据，普通的平衡树需要开n个节点，而WBLT需要开2n-1个 也就是说 储存上图的数据的treap长这样：  那么 相比之下它有什么好处呢？ ## 旋转 WBLT= Weight Balanced Tree（加权平衡树） + Leafy，其中Leafy已经在_定义和引入_中体现了，平衡是指一个节点的左子树和右子树大小近似相同，这样在查询/修改的时候才能做到近似log，旋转便是维护平衡的方便手段 因为其结构特殊 不需要像treap一样引入一个rand，只要旋转就可以维护其平衡。 先给出旋转的代码 ```cpp 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不同 ```cpp 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)$ ```cpp 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不同）。 ```cpp 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。 ```cpp 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 等等 旋转呢？ 我们在上文所有的操作中，似乎没有使用旋转，那旋转放在哪呢？ 我们将其放在树的结构有改变的地方，也就是插入 删除这些操作中，每当一个子树过大，就进行相应的旋转，在插入和删除操作中加入以下函数即可 ```cpp 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); } ``` 那么普通平衡树的代码如下 ```cpp #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数组即可） [代码](https://www.luogu.org/paste/5isx0y4z) ### P2596 [ZJOI2006]书架 平衡树部分还是个裸题 定义优先级越小，那本书就放越上面 设$a_i$为编号为$i$的书本的优先级，$mapp_i$为优先级为i的节点编号。 Top S:将优先级变为最小再插入 Bottom S：将优先级变为最大再插入 Insert S T：找到对应两本书 交换优先级 Ask S：查询优先级排名 Query S：查询第k小的优先级对应的编号 代码: ```cpp #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集训队论文里那个是双旋，是复杂度正确的。 最后用一张图结束本文吧  （发完引战言论就跑