一直觉得自己写作水平比较烂,而且现在也比较懒,大家凑活着看吧
前置知识:Top Tree相关理论
什么是Weight Balanced Top Tree?
就是满足重量平衡性质的Top Tree。
重量平衡的原始定义是,对于任意节点 $u$,其任意孩子节点 $v$,满足 $v$ 的子树大小 $size(v)$ 与 $u$ 的子树大小 $size(u)$ 的比值在常数范围内。
由于严格的重量平衡性质比较难以满足,这里将条件稍微放宽为,每个Top Tree中的节点向上走 $O(1)$ 后,所在节点的子树大小能翻常数倍。后面在一些问题上可以看到这个性质的用处。
静态树上的做法
可以发现流行的全局平衡二叉树就满足重量平衡的性质。
动态树上的做法:期望复杂度
每个点赋个随机权值,一个点的重儿子是子树max最大的那个儿子。
然后再对重链建treap,轻儿子也要用treap按乱序维护。
实链上的分裂合并就是treap的分裂合并,偏好儿子的切换就按子树max的来维护。
link/cut时需要一些额外讨论。
可以证明每个点期望深度为 $O(\log{n})$。
严格来说treap实现的版本不能算重量平衡树,但是在后续一些场景的分析中,表现跟严格复杂度的版本差不多。
动态树上的做法:严格复杂度
子问题:带权重量平衡树
使用平衡树维护带权序列,支持两种操作:
merge(L,x,R),x是单点。
split(A,k),表示将树A从位置k处分开。返回三元组(L,x,R),x是单点,L,R是相应前后缀组成的平衡树。
希望的复杂度:$O(\log\frac{|L|+w(x)+|R|}{w(x)})$ 复杂度维护平衡树的结构,其中 $w(x)$ 是节点 $x$ 的权重,$|L|,|R|$ 是 $L,R$ 的子树大小
维护不变量:
一个大小k的叶子必须在第i层,满足 $2^i<=k<2^{i+2}$。
任意一个第i层的块都要满足size严格小于 $2^{i+2}$。
第i层维护的块序列中,非叶的部分可以由第 $i-1$ 层中连续几个块(可以是一个)合并得到。第i层维护的块中,相邻两个块不能都小于 $2^i$。
可以验证,全树是重量平衡的(每个点往上走 $O(1)$ 步后size就会翻至少 $O(1)$ 倍),进而有两个推论:1.全树深度为 $O(\log{n})$; 2. x的深度为 $O(\log{\frac{n}{w(x)}})$
记一个块的秩为其所在的层,注意一个块所在的层是一个连续区间(因为允许父节点只有一个孩子,可以压起来),所以其秩也是一个连续区间,实现中可以仅存储其左右端点,而无需对每一层新建一个仅有一个儿子的节点。
shrink
传入参数为两个栈和一个中间元素,$st1,st2,a$
两个栈的栈中元素均满足秩从栈顶往下单调递增,并且 $a$ 的秩不超过两个栈的栈顶元素
可以想象a是秩的最低谷,两个栈是从谷底往两侧延伸的山丘,然后我们要从a开始一点一点把中间的坑填平,将栈中节点与 $a$ 一起合并为一棵合法的树。左右两侧的栈中元素需要满足一定的性质来保证能填平。
首先将 $a$ 的秩区间 $[r1,r2]$ 变成 $[r1,r1]$,避免 $a$ 的秩虚高
每次对于谷底所在的层i,要把连续的若干个秩为i的元素合并成秩为i+1的元素,执行如下贪心策略:
- 如果 $\frac{元素size和}{2^i}<8$,直接合并
- 如果按中位线分开可以分成2半且保证size不超限,按中位线均匀分
- 则先从左到右和从右到左各贪心地切尽量长的一刀,中间剩下的部分再直接贪心切
expand
传入一个栈s,栈中元素均为树中节点。返回另一个栈s',为将s的栈顶元素u弹掉后再将u的所有儿子按顺序加入栈
merge
将L入栈s。不断对执行 $s \leftarrow expand(s)$,直到s栈顶元素变成叶子或者栈顶元素的秩小于等于 $a$ 的秩。
对R同样操作,然后调用shrink。
split
先将树split成一个单点和两条链。直接将链入栈不可取,需要仿照merge中过程将链中元素给适当展开。
然后将左链和右链的链底的子树截下来,再调用shrink即可。
正确性
shrink过程中唯一可能违反性质的就是,某一轮填平谷底后新元素的size太小,并且此时栈顶元素(也就是未来第i层中的左右邻居)size也太小。
如果此时谷底元素已经有栈中元素参与合成了,由于栈中元素的size原本是满足条件的(是从合法的树中截出来的链),所以此时谷底元素的size一定也合法。
否则如果谷底元素size仍不合法,则在调用shrink前的过程中,栈顶元素一定会被不断expand直到合法。
完整版
用带权重量平衡树作为实链的数据结构,链剖策略使用严格重剖。注意轻子树也使用WCWBT来维护最重的儿子。
access
将一个点到根的链强制变为实链
drop
将实链上的轻边都抖落下去
注意access和drop为都需要注意轻重边切换的顺序,反了的话复杂度是错的;可以使用一个vector存储要切换的边最后再按正确顺序处理。
link/cut时需要一些额外讨论,细节这里略。
最后单次动态树操作的复杂度为严格 $O(\log{n})$,树结构上的静态查询跟普通Top Tree一样做即可。
WBTT能干什么
首先普通Top Tree能干的WBTT基本都能干
其次是一些特殊性质的问题
树分块类的问题
问题形式大概类似于 CTS2022 WBTT
用WBTT维护树结构,对于size小于 $B$ 的子树用 $O(size)$ 的代价维护信息;查询时递归到查询区间中所有size不超过 $B$ 的子树上即可。
重量平衡的性质保证了修改的复杂度,也保证了查询时只会递归到 $O(\frac{n}{B}+\log{n})$ 个子树上,单次复杂度 $O(\sqrt{n})$
以及实际上我们还可以比这题中做得更强,由于Top Tree还给出了块间分治结构,我们在上面跑fractional cascading的话,就可以单次 $O(\sqrt{n})$ 的复杂度解决区间rank上树的问题。
关于treap版本的复杂度分析,
一个引理是,如果树的大小<=B,则从单点 $i$ 往上合并信息的期望代价 $O(B)$。考虑 $j\gt i$ 对 $i$ 的贡献,期望是 $j$ 这个后缀出现的单调栈长度,等于 $H_{n-i+1}-H_{j-i+1}$,其中 $H_i$ 表示调和级数第 $i$项。对求和式稍微放缩一下,可以得到这是 $O(树的大小)$。
完整的分析细节比较冗长,这里略。
小修改动态树上的情形
大概类似于 wcriq 上树的版本,每次修改操作是从树中间裂出一个节点,要求保证单次最坏复杂度并且维护信息。
把wcriq里的做法改改也能上树,细节略。