OceanEye's Blog

是时候表演真正的技术了!

@OceanEye1年前

08/9
11:04
OI 模板——如果有哪里不对的请打死我

替罪羊树【复习向】

这是新坑……
同时开了KDT和LCT的坑【不知道的同学等下就知道了】

0x00

绝大多数的平衡树维持平衡是通过旋转操作
Merge_Split_Treap 是通过分裂合并维护堆的性质保持理论上的平衡
今天讲的替罪羊树是用来暴力维护子节点重量平衡的

0x01

某教程的传送门
另一个教程的传送门
这两个教程里面的说明都很有意思,可以看看

0x02

替罪羊树最神奇的地方就在于他的暴力重建
而且这个暴力重建是有时间复杂度保证的【势能分析那一套理论不是很懂,需要证明的可以去翻翻之前陈老师的论文】
保证每种平衡树的操作的时间复杂度在\(O(logN)\)的范围

替罪羊树还有一个小技巧
就是拍扁重建法
重建的时候先dfs把所有数放进一个数组,重建每一层递归都把mid拿出来当father即可
时间复杂度是O(size)的

最后讲的是替罪羊树的删除
因为这个树是没有旋转的
不能把它某个节点旋转到叶子然后把叶子节点删掉
所以用的是惰性删除
在删除的时候 打一个删除标记 表示“这个点被删除了 以后查询的时候直接跳过”
若一个子树内的惰性节点超出了某个范围【比如\(size*0.45\)】直接暴力重建

注意:
重建的时候带有删除标记的节点不能入数组
重建的两个条件
1.子树深度大于某个阈值 或 子树大小大于阈值 【实际上是等价的?】
2.子树内带有删除标记的节点大于阈值

0x03

代码
这份过了编译【就是不保证完全正确但是思路是对的】
状态好了来认真写一份……

替罪羊树【复习向】