WBLT（Weight Balanced Leafy Tree）学习笔记

· · 个人记录

CSP-J/S炸掉原地自闭不想写游记、我果然还是太菜、

回来肝专题了，幸好眼疾手快抢了一个比较容易 上头 上手而且看起来很友善的专题——WBLT。

参考资料：

鸣谢大佬：

本文不是一篇很正经的论文，仅供Leafy Tree入门学习参考。语言表达并不十分严谨，内容也可能存在错漏，如发现问题欢迎指正！

注：以下内容中“有效节点”的意思是这棵树维护的集合中的每个元素对应的点。

一、什么是Leafy Tree以及为什么要学习Leafy Tree

$Leafy\ Tree$在直观的形态上长什么样？ 直观地看，一棵普通的二叉搜索树长成这个样子： ![](https://t1.picb.cc/uploads/2019/11/23/kf70eg.png) 但是它对应的一棵$Leafy\ Tree$长成这个样子： ![](https://t1.picb.cc/uploads/2019/11/23/kf7S7X.md.png) 而只有蓝色的节点是有效的节点（即本来就有的节点） 所以，我们可以得到$Leafy\ Tree$的一个显著的缺点：**实际节点数量为有效节点（即叶子节点）的两倍**。 ~~这就是它叫Leafy Tree的原因？~~ 但是$Leafy\ Tree$也有很多优点，**和二叉搜索树相比，它的插入删除操作更容易实现；它还可以实现各种基于二叉树的数据结构，如其他平衡树，线段树，堆等。** --- # 二、如何用Leafy Tree实现二叉搜索树 在一棵$Leafy\ Tree$中，只有叶子节点是有效的节点。那么每个叶子节点的**值**就是它所对应的集合元素。而**对于一个非叶子节点，它的值定义为它的右儿子的值**。对于一棵左子树所有节点的值都小于右子树所有节点的值的树，就是一棵**二叉搜索树**。将这两者结合一下，我们就可以得到一棵$Leafy\ Tree$**实现的二叉搜索树**。它具有以下特点： 1. 左子树严格小于右子树 2. 每个非叶子节点的值为其右儿子的值（即整棵子树的最大值） 3. 每个叶子节点都是有效节点，每个非叶子节点都不是有效节点 （ ~~贴心的~~ 笔者把上面的图搬下来帮助理解） ![](https://t1.picb.cc/uploads/2019/11/23/kf7S7X.md.png) 这两个特点对$Leafy\ Tree$实现加权平衡树的理解有着很重要的作用。 根据以上特点，可以进行一些二叉搜索树的基本操作： ## 1.查找操作 查找操作非常容易实现。假如我们要查找一个值$x$在$Leafy\ Tree$中的位置，而当前我们处在位置$k$，那么根据定义，$k$的左儿子的值是整颗左子树的最大值，我们只需要比较$x$和$k$的左儿子的值，就可以知道$x$是属于$k$的左子树还是$k$的右子树了。接下来以此类推进行递归查找即可。查找方式类似于二叉搜索树。 同时，我们需要明确一个关于查找操作的特征：**查找操作找到的是大于等于$x$的最小的数**。 为什么？ 我们记$y$为查找$x$操作的返回值，则有： 情况1. 若$y<x$，那么查找$x$时就会去到离$y$最近的右兄弟子树（即比$y$靠右的兄弟子树）。因为在某个分岔路口，肯定会遇到$k$的左儿子的值（即$y$）小于$x$的情况，这时$x$就会往右走了。所以这种情况不成立。 情况2. 若在$Leafy\ Tree$上存在大于等于$x$的更小的数$z$，那么根据定义，$z$一定在$y$的左边。既然$x$会来到$y$，$x$就一定会大于$y$左边的所有节点。这与$z$的定义相悖。故$z$不存在。 综上，查找操作找到的就是大于等于$x$的最小的数啦。 ## 2.插入操作 每次插入的节点，根据$Leafy\ Tree$的定义，肯定是叶子节点。所以我们就要将其插入到一个合适的位置作为该树叶子节点。 如何找到一个合适的位置呢？ 我们进行查找操作找到跟要插入的数$x$的值最接近的叶子节点$y$。那么我们的$x$肯定是要插到$y$这个节点下面作为叶子节点。但是如果直接将$x$插入到$y$下面，就违反了$Leafy\ Tree$的定义：每个节点要么没有儿子节点，要么有两个儿子节点。同时，$y$原来也是一个叶子节点啊，这么插入后，$y$本身的值不就被覆盖掉了吗？ 其实，我们只要新建两个叶子节点作为$y$的孩子节点，一个保存$x$的值，一个保存$y$原来的值就可以了。这样做既不会与原本的定义矛盾，$y$的值也能得以保存。 ## 3.删除操作 根据$Leafy\ Tree$的定义，要被删除的点肯定都是叶子节点（因为其他节点都是我们为了方便地实现$Leafy\ Tree$的功能而自己加上去的，无实际意义）。 我们进行查找操作找到那个要被删除的点，接下来怎么办呐？只是很高兴地把它删除掉，然后就完事了吗？很显然，这样做是不行的。因为如果只是单纯地删除掉这个点，它的父亲节点不就只剩下一个儿子了吗？这样就不符合$Leafy\ Tree$的定义了。记住：**为了使$Leafy\ Tree$这个数据结构真正发挥它的作用，我们就要时时刻刻维护好它的定义。** 其实，删除掉这个点后的操作也十分简单。你想，如果一个点只有一个儿子，而且这个点本身没有实际意义（即不是有效节点），那么它的儿子不就可以取代它的位置了吗？ 所以我们把一个点删除掉以后，用这个点的兄弟节点（根据定义，这个点一定是存在兄弟节点的）取代父亲节点的位置，这样就能维护好$Leafy\ Tree$的性质啦。 --- - 可以发现，由于用到了只有叶子节点维护信息的性质，Leafy Tree 进行插入删除相当方便。每次插入删除的节点实际上都是叶子节点，大量减少了普通二叉搜索树结构中对插入删除的节点类型的繁杂讨论（即这个节点是叶子节点，还是有一个儿子，还是有两个儿子）。同时由于每个非叶子节点维护了区间信息，通过左儿子的区间信息来进行定位，本质上和二叉搜索树通过与树根节点的值比较进行定位相同，所以是以更加简洁的实现达到了同样的效果。（摘自王思齐《Leafy Tree 及其实现的加权平衡树》） --- # 三、什么是加权平衡树及什么是WBLT ## 1.加权平衡树 **加权平衡树**(Weight Balanced Tree，也叫$BB[α]$树或重量平衡树)，是一种**储存子树大小的二叉搜索树**。每个节点的权重$weight$取决于或等于以它为根节点的子树的大小。对于每个节点，满足**该节点的$weight$等于该节点左右儿子的$weight$之和**。 - 如果一个节点$x$满足$min(weight[x.left],weight[x.right])≥α·weight[x]$，则称这个节点是$α$**加权平衡**的。根据树的定义，有$0<α≤\frac{1}{2}$。（摘自王思齐《Leafy Tree 及其实现的加权平衡树》） 这个定义也十分重要，这是我们以后判断一棵树是否平衡的关键。 ## 2.WBLT **WBLT**(Weight Balanced Leafy Tree) 是加权平衡的$Leafy\ Tree$。由于其实现方式类似于线段树，故也有人称之为“线段平衡树”。 它虽然要开两倍的空间，但可以在**较短的代码**中，**实现平衡树的大多数功能**，而且**常数较小，可以可持久化**。 本文要重点介绍的就是WBLT。 --- # 四、如何实现WBLT 以下介绍了如何用$Leafy\ Tree$实现一些平衡树的基本操作。 ## 1.维护平衡 对于一棵平衡树，只有时刻保持平衡才能在众多数据结构中脱颖而出成为一个较优秀的算法。而维护平衡的方法主要有两种：重构（如替罪羊树）和旋转（如$Splay$）。 重构实现平衡笔者接触不多（一开始学平衡树学的是$Splay$），所以在这里就只介绍旋转的方法啦（不过好像大多都是用旋转实现平衡）。 对于一棵子树，我们可以用常数$α$来判断其是否平衡（具体判断方法见上文）。如果不平衡的话，就旋转维护平衡。如何旋转呢？ 来看一个例子：下面是一棵明显不平衡（左子树偏重）的$Leafy\ Tree$（注意，**圈内的数字是编号，不是值或权重**） ![](https://t1.picb.cc/uploads/2019/11/27/k60Tww.png) 既然是左子树偏重，那我们就可以把左儿子$2$按照和$Splay$类似的方法（父亲节点变自己的右儿子，自己的右儿子变父亲节点的左儿子）右旋上去，变成这样： ![](https://t1.picb.cc/uploads/2019/11/27/k6Kr3W.png) 就可以达到相对变平衡的目的啦~而如果我们每一棵子树都是相对平衡的，那不就可以说这棵平衡树是相对平衡的了嘛？这样它就可以跑得很快啦~ 还要注意了，如果像这样进行旋转操作，是**需要向上维护**的（因为这棵子树的根节点都换了嘛）。 如果上面的部分你已经全部处理好了，那么你可以选择在这里$continue$这块内容了。因为接下来只是一点减小码量的小技巧而已~ ------------ 由于向上维护其实还是有点麻烦的，所以我们可以想办法稍微使这个旋转没那么麻烦。我们观察到，其实下面的相对子树是没有变化的，而只有$5$变成了右子树根节点的左儿子。那么，我们是不是可以直接把$5$接到右子树的左儿子呢？ ![](https://t1.picb.cc/uploads/2019/11/27/k6KjIe.png) 你可能会想，这样的话，左子树不就只剩一个儿子了嘛？而且右子树也只有一个儿子啊？万一右子树原来是有两个儿子的，那它原来的左儿子不就不翼而飞了嘛？ 其实，我们可以把将左子树的右儿子变成右子树的左儿子理解为删掉了左子树根节点的右儿子，并为右子树根节点添一个左儿子。那么，就可以直接用插入删除的办法将左子树的右儿子变成右子树的左儿子啦~ ![](https://t1.picb.cc/uploads/2019/11/27/k60R9W.png) 你可能已经发现这种做法有一个弊端：那就是每次旋转都要新增一个节点。在$Leafy\ Tree$这种“寸土寸金”的数据结构中，这无疑就是玩命啊！ 但是，相对于繁杂的维护，这种方法会简洁许多；而且我们可以用“垃圾回收”，把删除掉的节点的编号回收重新利用，这样能将节点编号的大小控制在$2n$以内。 ```cpp inline void rotate(int x,bool p) { if(p) { int l=tr[x].l; tr[x].r=ins(tr[l].r,tr[x].r); tr[x].l=tr[l].l;vclean(l); } else { int r=tr[x].r; tr[x].l=ins(tr[x].l,tr[r].l); tr[x].r=tr[r].r;vclean(r); } } inline bool pd(int x){return((double)(min(tr[tr[x].l].size,tr[tr[x].r].size))>=A*(double)(tr[x].size));} inline void maintain(int x) { if(pd(x))return; rotate(x,tr[tr[x].l].size>tr[tr[x].r].size); } ``` ## 2.插入和删除操作 跟$Leafy\ Tree$实现二叉平衡树的方法一样，就不多赘述了。 ```cpp void add(int now,int x) { if(tr[now].size==1) { tr[now].l=vnew(min(tr[now].c,x)); tr[now].r=vnew(max(tr[now].c,x)); pushup(now);return; } maintain(now); int l=tr[now].l,r=tr[now].r; if(x<=tr[l].c)add(l,x);else add(r,x);pushup(now); } void del(int now,int fa,int x) { if(tr[now].size==1) { int newone=(tr[fa].l==now)?tr[fa].r:tr[fa].l; vcopy(newone,fa);vclean(now);vclean(newone);return; } maintain(now); int l=tr[now].l,r=tr[now].r; if(x<=tr[l].c)del(l,now,x);else del(r,now,x);pushup(now); } ``` ## 3.查找$x$数的排名 查找$x$数的排名，其实就是查找$x$前面有多少个数。根据二叉搜索树的定义，每次往右走的时候，左子树的所有数肯定都比$x$要小。所以我们可以按照二叉搜索树的方法去查找$x$（根据该操作的要求，一定能找到），每次往右走的时候把左子树的大小加上就可以了。 ```cpp int findrank(int now,int x) { if(tr[now].size==1)return 1;maintain(now); int l=tr[now].l,r=tr[now].r; if(x<=tr[l].c)return findrank(l,x); else return tr[l].size+findrank(r,x); } ``` ## 4.查找排名为$k$的数 查找排名为$k$的数，其实就是查找前面有$k-1$个数的数的值。和查找$x$数的排名同理，我们按照二叉搜索树的搜索方法，如果左子树的大小大于等于当前的$k$，就往左走，否则就往右走。要注意，往右走时$k$要减去左子树的大小。 ```cpp nt findshuz(int now,int k) { if(tr[now].size==k)return tr[now].c; maintain(now);int l=tr[now].l,r=tr[now].r; if(k<=tr[l].size)return findshuz(l,k); else return findshuz(r,k-tr[l].size); } ``` ## 5.查找前驱 根据前面$Leafy\ Tree$实现二叉搜索树的查找操作的分析，查找操作找到的是大于等于$x$的最小的数。那么，由于查找$x$数的排名的操作和查找操作的查找方法是相同的，所以查找$x$数的排名也具有该特征。所以，我们只需要找到$x$**的排名，该排名减一所对应的数**就是小于$x$的最大的数——也就是$x$的前驱了。 ```cpp inline int Q(int x){return findshuz(1,findrank(1,x)-1);} ``` ## 6.查找后继 根据前面$Leafy\ Tree$实现二叉搜索树的查找操作的分析，查找操作找到的是大于等于$x$的最小的数。那么，由于查找$x$数的排名的操作和查找操作的查找方法是相同的，所以查找$x$数的排名也具有该特征。所以，我们只需要找到$(x+1)$**的排名，该排名对应的数**就是大于$x$的最大的数——也就是$x$的后继了。 为什么？ 当$x$在$Leafy\ Tree$中存在的时候，查找$x$数的排名操作就会找到$x$的排名，而这个排名所对应的数等于$x$，不满足后继的定义。而如果是查找$(x+1)$数的排名，就会找到一个大于等于$(x+1)$的最小的数。这个数一定就是$x$的后继了，因为值都是整数，所以在$Leafy\ Tree$上找不到一个大于$x$并且小于 $Leafy\ Tree$上大于等于$(x+1)$的最小的数 的数了。 当$x$在$Leafy\ Tree$中不存在的时候，查找$x$数的排名操作和查找$(x+1)$的排名操作返回值一样——都是一个在$Leafy\ Tree$上大于等于$(x+1)$的最小的数。 ```cpp inline int H(int x){return findshuz(1,findrank(1,x+1));} ``` --- # 五、关于运行速度 我一向都不会关于时间复杂度的证明，先搬论文，具体方面等我学会了再填坑。 ![](https://cdn.luogu.com.cn/upload/image_hosting/xi6enlrf.png) （图片来源：王思齐《Leafy Tree 及其实现的加权平衡树》） --- # 六、关于WBLT的例题和练习 ## 0.一点前言 如果上面的内容你已经理解得差不多了，可以自己去找题做，一般平衡树相关的题目都可以尝试。这里提供的题目仅供参考。 --- ## 1.普通平衡树 首先当然是模板题，根据上文介绍的方法直接套即可。 提交地址： [洛谷P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369) [2415: 【Leafy Tree】普通平衡树](http://10.3.20.18:81/problem.php?id=2415) [LOJ#104. 普通平衡树](https://loj.ac/problem/104) **code:** ```cpp #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100000+10;const double A=1.0/3.0; //A即α，用于判断WBLT是否平衡的常数 struct node{int l,r,size,c;}tr[2*N];int len,root,sta[N],tp; //l,r分别代表一个节点的左右孩子；size为该节点所管辖的叶子节点的个数；c为该节点的值 inline int ins(int l,int r)//新建一个非叶子节点，该节点的左右儿子分别是l和r { int now=tp?sta[tp--]:++len; tr[now].l=l;tr[now].r=r;tr[now].c=tr[r].c; tr[now].size=tr[l].size+tr[r].size;return now; } //vclean：节点回收（两倍节点的leafy tree对于空间是很珍惜的） inline void vclean(int x){sta[++tp]=x;tr[x].l=tr[x].r=tr[x].c=tr[x].size=0;} //vcopy：复制节点 inline void vcopy(int y,int x){tr[x].l=tr[y].l;tr[x].r=tr[y].r;tr[x].size=tr[y].size;tr[x].c=tr[y].c;} //vnew：新建一个叶子节点，其值为c inline int vnew(int c){int now=tp?sta[tp--]:++len;tr[now].size=1;tr[now].c=c;return now;} //pushup：维护节点信息（参考线段树） inline void pushup(int x) { int l=tr[x].l,r=tr[x].r;if(!tr[l].size)return; tr[x].c=tr[r].c;tr[x].size=tr[l].size+tr[r].size; } //rotate：旋转维护平衡 inline void rotate(int x,bool p) { if(p) { int l=tr[x].l; tr[x].r=ins(tr[l].r,tr[x].r); tr[x].l=tr[l].l;vclean(l); } else { int r=tr[x].r; tr[x].l=ins(tr[x].l,tr[r].l); tr[x].r=tr[r].r;vclean(r); } } //pd：判断子树x是否平衡 inline bool pd(int x){return((double)(min(tr[tr[x].l].size,tr[tr[x].r].size))>=A*(double)(tr[x].size));} //maintain：维护子树平衡 inline void maintain(int x) { if(pd(x))return; rotate(x,tr[tr[x].l].size>tr[tr[x].r].size); } //add：插入x数（平衡树基本操作） void add(int now,int x) { if(tr[now].size==1) { tr[now].l=vnew(min(tr[now].c,x)); tr[now].r=vnew(max(tr[now].c,x)); pushup(now);return; } maintain(now); int l=tr[now].l,r=tr[now].r; if(x<=tr[l].c)add(l,x);else add(r,x);pushup(now); } //del：删除x数（平衡树基本操作） void del(int now,int fa,int x) { if(tr[now].size==1) { int newone=(tr[fa].l==now)?tr[fa].r:tr[fa].l; vcopy(newone,fa);vclean(now);vclean(newone);return; } maintain(now); int l=tr[now].l,r=tr[now].r; if(x<=tr[l].c)del(l,now,x);else del(r,now,x);pushup(now); } //findrank：查询x数的排名（平衡树基本操作） int findrank(int now,int x) { if(tr[now].size==1)return 1;maintain(now); int l=tr[now].l,r=tr[now].r; if(x<=tr[l].c)return findrank(l,x); else return tr[l].size+findrank(r,x); } //findshuz：查询排名为x的数（平衡树基本操作） int findshuz(int now,int k) { if(tr[now].size==k)return tr[now].c; maintain(now);int l=tr[now].l,r=tr[now].r; if(k<=tr[l].size)return findshuz(l,k); else return findshuz(r,k-tr[l].size); } int main() { int n;scanf("%d",&n); root=vnew(1<<30);//建一个不会被改动的根节点，避免了判断树是否为空的麻烦 for(int i=1;i<=n;i++) { int opt,x;scanf("%d%d",&opt,&x); if(opt==1)add(root,x); else if(opt==2)del(root,0,x); else if(opt==3)printf("%d\n",findrank(root,x)); else if(opt==4)printf("%d\n",findshuz(root,x)); else if(opt==5)printf("%d\n",findshuz(root,findrank(root,x)-1)); //寻找前驱：在WBLT中：findshuz(x)函数找到的是大于等于x的最小的数。该数的排名-1即为x的前驱。 else printf("%d\n",findshuz(root,findrank(root,x+1))); //寻找后继：在WBLT中：findshuz(x)函数找到的是大于等于x的最小的数。findshuz(x+1)即为x的后继。 } return 0; } ``` --- ## 2.鬼子进村（超自然力量） 提交地址： [洛谷P1503 鬼子进村](https://www.luogu.com.cn/problem/P1503) [caioj2416: 【Leafy Tree】超自然力量](http://10.3.20.18:81/problem.php?id=2416) 将被摧毁的房子加进Leafy Tree中，查找最多可以到达多少个房子，即查找前驱和后继，相减即为答案。 **code:** ```cpp #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=50000+10; struct node{int l,r,c,size;}tr[2*N]; int sta[N],tp,len;const double A=1.0/3.0; /*此处省略，WBLT部分同上*/ int zha[N],top,n,m;bool v[N]; int main() { scanf("%d%d",&n,&m); memset(sta,0,sizeof(sta));tp=0; memset(zha,0,sizeof(zha));top=0; memset(v,0,sizeof(v));add(vnew(0),n+1); for(int i=1;i<=m;i++) { char s[10];int x; scanf("%s",s); if(s[0]=='D') { scanf("%d",&x);zha[++top]=x; add(1,x);v[x]=1; } else if(s[0]=='R'){x=zha[top--];v[x]=0;del(1,0,x);} else { scanf("%d",&x); if(v[x])printf("0\n"); else { int q=findshuz(1,findrank(1,x)-1),p=findshuz(1,findrank(1,x+1)); printf("%d\n",p-q-1); } } } return 0; } ``` --- ## 3.书架 提交地址： [caioj2417: 【Leafy Tree】书架](http://10.3.20.18:81/problem.php?id=2417) [洛谷P2596 [ZJOI2006]书架](https://www.luogu.com.cn/problem/P2596) 设 $p[x]$：编号$x$的位置 $q[x]$：位置$x$的编号 $left$初始值为$m+1 right$初始值为$n+m+1
  1. 对于Top操作，删除p[x]；q[p[x]]=0；插入left-1；left--。p[x]=left，q[left]=x
  2. 对于Bottom操作，删除p[x]；q[p[x]]=0；插入right+1；right++。p[x]=right，q[right]=x
  3. 对于Insert操作：
    • T=0$ -> $continue
    • - $T>0$ -> 记$Y=p[x]$的后继; - $T<0$ -> 记$Y=p[x]$的前驱;
    • X=p[x]$；$y=q[Y]$；$swap(p[x],p[y])$；$swap(q[X],q[Y])
  4. 对于Ask操作，输出p[x]的排名-1
  5. 对于Query操作，输出q[树上排名为x的位置] （此处的“位置”指的不是书架上的位置，可以理解为“优先级”）

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double A=1.0/3.0;
const int N=80000+10,inf=0x3f3f3f3f;
struct node{int l,r,c,size;}tr[2*N];
int len,sta[N],tp,left,right;
/*此处省略，WBLT部分同上*/
int Q(int x,int k){return findshuz(1,findrank(1,x)+k);}
int p[3*N],q[3*N];
int main()
{
    int n,m,x,id;scanf("%d%d",&n,&m);
    left=m;right=n+m+1;vnew(inf);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);id=left+i;
        p[x]=id;q[id]=x;add(1,id);
    }
    while(m--)
    {
        char s[10];scanf("%s",s);
        if(s[0]=='T')
        {
            scanf("%d",&x);
            del(1,0,p[x]);q[p[x]]=0;
            add(1,left);p[x]=left;q[left]=x;left--;
        }
        else if(s[0]=='B')
        {
            scanf("%d",&x);
            del(1,0,p[x]);q[p[x]]=0;
            add(1,right);p[x]=right;q[right]=x;right++;
        }
        else if(s[0]=='I')
        {
            scanf("%d%d",&x,&id);
            if(!id)continue;
            int X=p[x],Y=Q(p[x],id),y=q[Y];
            swap(p[x],p[y]);swap(q[X],q[Y]);
        }
        else if(s[0]=='A'){scanf("%d",&x);printf("%d\n",findrank(1,p[x])-1);}
        else{scanf("%d",&x);printf("%d\n",q[findshuz(1,x)]);}
    }
    return 0;
}

4.营业额统计

提交地址：

洛谷P2234 [HNOI2002]营业额统计

caioj2418: 【Leafy Tree】营业额统计

对于每天的最小波动值，我们找到当天的营业额在树上的前驱和后继，比较它和前驱、后继的差的绝对值，更小的那个即为当天的最小波动值。注意要特判没有前驱或者后继的情况，以及别忘了记录以后要把当天的营业额加进树中！

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double A=1.0/3.0;
const int N=100000+10,inf=0x3f3f3f3f;
struct node{int l,r,c,size;}tr[2*N];
int len,sta[N],tp;
/*此处省略，WBLT部分同上*/
inline int Q(int x){return findshuz(1,findrank(1,x)-1);}
inline int H(int x){return findshuz(1,findrank(1,x));}
int main()
{
    int n,ans,x;scanf("%d",&n);
    add(vnew(inf),-inf);scanf("%d",&x);add(1,x);ans=x;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        int q=Q(x),h=H(x);
        if(q==-inf)ans+=abs(x-h);
        else if(h==inf)ans+=abs(x-q);
        else ans+=min(abs(x-q),abs(x-h));
        add(1,x);
    }
    printf("%d\n",ans);
    return 0;
}

5.可持久化平衡树

提交地址：

洛谷P3835 【模板】可持久化平衡树

caioj2419: 【Leafy Tree】可持久化平衡树

用WBLT实现可持久化，只需在修改时进行Path Copy——每次要修改一个点时，我们将根到这条点的路径上所有被修改过的点都依次新建一个节点，查找时从不同的根出发即可。

注意空间的大小要开大一点，因为Path Copy还是很占空间的。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double A=1.0/3.0;
const int N=500000+10;const long long inf=1ll<<31-1ll;
struct node{int l,r,c,size;}tr[25*N];
int len,sta[N],tp;
/*快读*/
/*此处省略，WBLT部分同上*/
int add(int now,int c)
{
    if(tr[now].size==1)
    {
        int Now=vnew(tr[now].c);
        tr[Now].l=vnew(min(tr[Now].c,c));
        tr[Now].r=vnew(max(tr[Now].c,c));
        pushup(Now);return Now;
    }
    maintain(now);
    int l=tr[now].l,r=tr[now].r;
    if(c<=tr[l].c)return ins(add(l,c),r);
    else return ins(l,add(r,c));
}
int del(int now,int fa,int c)
{
    if(tr[now].size==1)return (tr[now].c!=c)?now:-1;
    maintain(now);
    int l=tr[now].l,r=tr[now].r;
    if(c<=tr[l].c)
    {
        int d=del(l,now,c);
        return d==-1?r:ins(d,r);
    }
    else
    {
        int d=del(r,now,c);
        return d==-1?l:ins(l,d);
    }
}
int root[N];
inline int Q(int rt,int x){return findshuz(rt,findrank(rt,x)-1);}
inline int H(int rt,int x){return findshuz(rt,findrank(rt,x+1));}
int main()
{
    int n;read(n);root[0]=0;
    root[0]=vnew(int(inf));
    for(int i=1;i<=n;i++)
    {
        int opt,la,x;read(la);read(opt);read(x);
        root[i]=root[la];
        if(opt==1)root[i]=add(root[la],x);
        else if(opt==2)root[i]=del(root[la],0,x);
        else if(opt==3)printf("%d\n",findrank(root[i],x));
        else if(opt==4)printf("%d\n",findshuz(root[i],x));
        else if(opt==5)
        {
            int q=Q(root[i],x);
            printf("%d\n",q<x?q:int(-inf));
        }
        else
        {
            int h=H(root[i],x);
            printf("%d\n",h>x?h:int(inf));
        }
    }
    return 0;
}

6.郁闷的出纳员

提交地址：

caioj2420: 【Leafy Tree】郁闷的出纳员

洛谷P1486 [NOI2004]郁闷的出纳员

这道题主要是实现平衡树的子树删除（对于每一次减工资，找到工资下限的位置（若没有就找到它的后继），然后删除其左边的节点即可）。

之前接触伸展树时，子树删除非常的方便——只需要找到工资下限（或者它的后继）的位置，然后将其旋转到根节点，直接cut掉它的左儿子即可。但是由于我们的Leafy\ Tree需要严格维护每个节点要么有两个儿子，要么没有儿子这一特点，而且Leafy\ Tree没有将一个节点旋转到根节点（即Splay）这种操作，我们需要对删除方法进行一些改动。

同样是找到工资下限（或者它的后继）的位置，不同的是进行搜索的过程中，如果遇到往右儿子走的情况，就直接复制右儿子的信息点到自己身上。这样就可以实现删除左儿子了。记得别忘了回收节点（大空间Leafy Tree伤不起、、）

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200100+10;
const double A=1.0/3.0;
struct node{int l,r,c,size;}tr[2*N];
int len,sta[2*N],tp,Min,ans,root;
/*此处省略，WBLT部分同上*/
void bigclean(int x)
{
    if(!x)return;
    bigclean(tr[x].l);bigclean(tr[x].r);
    clean(x);
}
void del(int now,int x)
{
    if(tr[now].size==1)return;
    maintain(now);int l=tr[now].l,r=tr[now].r;
    if(x<=tr[l].c)del(l,x);
    else
    {
        ans+=tr[l].size;bigclean(l);
        tr[now]=tr[r];clean(r);del(now,x);
    }
    pushup(now);
}
void change(int c,int now)
{
    if(!now)return;tr[now].c+=c;
    change(c,tr[now].l);change(c,tr[now].r);
}
int main()
{
    int n,x;scanf("%d%d",&n,&Min);ans=0;
    root=vnew(0x3f3f3f3f);
    while(n--)
    {
        char s[10];scanf("%s%d",s,&x);
        if(s[0]=='I'){if(x>=Min)add(root,x);}
        else if(s[0]=='A')change(x,root);
        else if(s[0]=='S')
        {
            change(-x,root);
            del(root,findshuz(root,findrank(root,Min)));
        }
        else
        {
            int siz=tr[root].size-1;
            if(x>siz)printf("-1\n");
            else printf("%d\n",findshuz(root,siz-x+1));
        }
    }
    printf("%d\n",ans);
    return 0;
}

7.二逼平衡树

提交地址：

洛谷P3380 【模板】二逼平衡树（树套树）

caioj2421: 【Leafy Tree】二逼平衡树

bzoj3196: Tyvj 1730 二逼平衡树

众所周知 这是一道树套树的模板题。我们观察题意，容易想到区间查找对于一棵平衡树是不现实的，所以我们用线段树套平衡树。对于线段树的每一个节点，都建一棵平衡树，然后就可以很方便地进行修改和查找了。

而对于平衡树部分，此时我们的Leafy\ Tree就有优势了——码量不大，速度也比较快（虽然空间限制是擦着边过的、、）。

这是用伸展树来实现的，它不开O2过不了！（当然，可能是我的伸展树打得不够优秀、、）

而这个是用Leafy\ Tree实现的，还算比较快，而且不吸氧也能过。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double A=1.0/3.0;
const int N=50000+10,inf=2147483647;
struct segtree{int l,r,lc,rc,c;}tr[2*N];
struct node{int l,r,c,size;}Tr[100*N];
int seglen,a[N],len,sta[100*N],tp;
/*此处省略，WBLT部分同上*/
int findrank(int now,int c)
{
    if(Tr[now].size==1)return Tr[now].c<c;
    maintain(now);
    int l=Tr[now].l,r=Tr[now].r;
    if(c<=Tr[l].c)return findrank(l,c);
    else return Tr[l].size+findrank(r,c);
}
inline int Q(int root,int x)
{
    int R=findrank(root,x);
    return !R?-inf:findshuz(root,R);
}
inline int H(int root,int x){return findshuz(root,findrank(root,x+1)+1);}
inline int blt(int l,int r)
{
    int root=vnew(inf);
    for(int i=l;i<=r;i++)add(root,a[i]);
    return root;
}
void bt(int l,int r)
{
    seglen++;int now=seglen;
    tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;
    tr[now].c=blt(l,r);
    if(l<r)
    {
        int mid=(l+r)/2;
        tr[now].lc=seglen+1;bt(l,mid);
        tr[now].rc=seglen+1;bt(mid+1,r);
    }
}
void change(int now,int x,int k)
{
    add(tr[now].c,k);del(tr[now].c,0,a[x]);
    if(tr[now].l==tr[now].r)return;
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(x<=mid)change(lc,x,k);
    else change(rc,x,k);
}
int Rank(int now,int l,int r,int k)
{
    if(tr[now].l==l&&tr[now].r==r)return findrank(tr[now].c,k);
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(r<=mid)return Rank(lc,l,r,k);
    else if(mid+1<=l)return Rank(rc,l,r,k);
    else return Rank(lc,l,mid,k)+Rank(rc,mid+1,r,k);
}
int shuz(int l,int r,int k)
{
    int L=0,R=inf,ans=0;
    while(L<=R)
    {
        int mid=(L+R)/2;
        if(Rank(1,l,r,mid)+1<=k)L=mid+1,ans=mid;
        else R=mid-1;
    }
    return ans;
}
int findQ(int now,int l,int r,int k)
{
    if(tr[now].l==l&&tr[now].r==r)return Q(tr[now].c,k);
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(r<=mid)return findQ(lc,l,r,k);
    else if(mid+1<=l)return findQ(rc,l,r,k);
    else return max(findQ(lc,l,mid,k),findQ(rc,mid+1,r,k));
}
int findH(int now,int l,int r,int k)
{
    if(tr[now].l==l&&tr[now].r==r)return H(tr[now].c,k);
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(r<=mid)return findH(lc,l,r,k);
    else if(mid+1<=l)return findH(rc,l,r,k);
    else return min(findH(lc,l,mid,k),findH(rc,mid+1,r,k));
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    bt(1,n);
    while(m--)
    {
        int opt,l,r,k;scanf("%d",&opt);
        if(opt==3)
        {
            scanf("%d%d",&l,&k);
            change(1,l,k);a[l]=k;
        }
        else
        {
            scanf("%d%d%d",&l,&r,&k);
            if(opt==1)printf("%d\n",Rank(1,l,r,k)+1);
            else if(opt==2)printf("%d\n",shuz(l,r,k));
            else if(opt==4)
            {
                int q=findQ(1,l,r,k);
                printf("%d\n",q<k?q:-inf);
            }
            else
            {
                int h=findH(1,l,r,k);
                printf("%d\n",k<h?h:inf);
            }
        }
    }
    return 0;
}

8.可持久化数组

提交地址：

洛谷P3919 【模板】可持久化数组（可持久化线段树/平衡树）

忽略二叉搜索树性质，直接用下标区分位置。然后套可持久化即可。建议先做这题再做可持久化平衡树（这题会简单一些）。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double A=1.0/3.0;
const int N=1000000+10;
struct node{int l,r,c,size;}tr[20*N];
int len,sta[N],tp;
/*此处省略，WBLT部分同上*/
int change(int now,int k,int c)
{
    if(tr[now].size==1)return vnew(c);
    maintain(now);int l=tr[now].l,r=tr[now].r;
    if(k<=tr[l].size)return ins(change(l,k,c),r);
    else return ins(l,change(r,k-tr[l].size,c));
}
void add(int now,int c)
{
    if(tr[now].size==1)
    {
        tr[now].l=vnew(tr[now].c);
        tr[now].r=vnew(c);pushup(now);return;
    }
    maintain(now);add(tr[now].r,c);pushup(now);
}
int find(int now,int k)
{
    if(tr[now].size==k)return tr[now].c;
    maintain(now);int l=tr[now].l,r=tr[now].r;
    if(k<=tr[l].size)return find(l,k);
    else return find(r,k-tr[l].size);
}
int root[N];
int main()
{
    int n,m,x;scanf("%d%d%d",&n,&m,&x);
    root[0]=vnew(x);for(int i=1;i<n;i++)scanf("%d",&x),add(root[0],x);
    for(int i=1;i<=m;i++)
    {
        int v,opt,ip,c;scanf("%d%d%d",&v,&opt,&ip);
        root[i]=root[v];
        if(opt==1){scanf("%d",&c);root[i]=change(root[v],ip,c);}
        else printf("%d\n",find(root[i],ip));
    }
    return 0;
}

9.报表统计

提交地址：

洛谷P1110 [ZJOI2007]报表统计

caioj2422: 【Leafy Tree】报表统计

我们维护两个堆（可以用stl的优先队列），一个储存所有元素中最接近的两个元素的差值（绝对值），一个储存相邻两个元素的之间差值（绝对值）的最小值。每次将一个数插入到合适的位置（可以用链表方便地实现），把之前的相邻差值从堆中删除，再向队中加入两个新的差值（分别为新的数和它前面的、它后面的数的差值的绝对值）。在WBLT上用和营业额统计查找方法相同的方法查找对于这个新数而言的最小差值并将它插入堆中，输出时输出堆顶即可。

对于在堆中删除任意的数，我们可以用另外一个堆，储存要删除的数。当两个堆的堆顶相同时，就同时pop即可。

code:

#pragma GCC optimize("Ofast")
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double A=1.0/3.0;
const int N=500000+10,inf=0x3f3f3f3f;
struct node{int l,r,c,size;}tr[10*N];
int len,sta[2*N],tp,rt;
/*快读*/
/*此处省略，WBLT部分同上*/
inline int Q(int x){return findshuz(rt,findrank(rt,x)-1);}
inline int H(int x){return findshuz(rt,findrank(rt,x));}
priority_queue<int>q,d1,d2;
inline void delet(int d)
{
    d2.push(d);
    while(d1.size()&&d2.size()&&d1.top()==d2.top()){d1.pop();d2.pop();}
}
struct lb{int last,next,end,s;}b[2*N];int ln;
int main()
{
    int n,m,x;read(n);read(m);ln=n;
    rt=vnew(inf);add(rt,-inf);
    for(register int i=1;i<=n;i++)
    {
        read(x);b[i].s=x;b[i].end=i;
        if(i!=1)b[i-1].next=i,b[i].last=i-1,d1.push(-abs(b[i].s-b[i-1].s));
        if(i!=n)b[i+1].last=i,b[i].next=i+1;
        if(!q.size()||q.top()){int m1=Q(x),m2=H(x),z=min(abs(x-m1),abs(x-m2));q.push(-z);}
        add(rt,x);
    }
    while(m--)
    {
        char s[20];scanf("%s",s);
        if(s[0]=='I')
        {
            int x,c,e,en,t=++ln;read(x);read(c);
            e=b[x].end;en=b[e].next;b[t].s=c;b[x].end=t;
            if(en)b[en].last=t,b[t].next=en,d1.push(-abs(b[en].s-c));
            if(e)b[e].next=t,b[t].last=e,d1.push(-abs(c-b[e].s));
            if(e&&en)delet(-abs(b[en].s-b[e].s));
            if(!q.size()||q.top()){int m1=Q(c),m2=H(c),z=min(abs(c-m1),abs(c-m2));q.push(-z);}
            add(rt,c);
        }
        else
        {
            if(s[4]=='G')printf("%d\n",-d1.top());
            else printf("%d\n",-q.top());
        }
    }
    return 0;
}

七、尾声

（听说7是笔者最喜欢的数字，也是一个充满魔力的数字，那就到此为止吧）

对于Leafy Tree及其实现的加权平衡树的专题学习暂时就告一段落了。它是一个很优秀且平易近人的数据结构（虽然参考资料不多）。在这个过程中我也学到了很多。再次感谢所有在我学习过程中给予过我帮助的人。也希望这篇学习笔记能给你一点点帮助。