势能平衡树,单侧递归平衡树,平衡树优化建图
jsq1004
·
·
算法·理论
问题引入
先来看几个问题:
- 线段树 3,but 在动态树上。
- 区间加、区间最大子段和,but 还支持区间翻转。
- 维护前缀最大值的个数,but 在动态树上。
- 维护前缀最大值之和,but 需要支持区间
chkmin 和区间加。
- 给定树上若干个点,要求这些点的点权必须大于其邻域内的点权,构造一组满足条件的方案。
势能线段树的复杂度证明
吉司机线段树:令 \sum_x [mx_x \ne mx_{fa}] 为势能。
发现每当一个点被暴力向下递归时,他某个后代的势能就会减少 1,(因为存在 mx_x 和 se_x 就说明有一个后代的 mx_v = se_x,那个点就和父亲不一样,然后现在那个点要被抹平)。
一势能最多带来 O(\log n) 的复杂度(最差一条链服务一个点)
区间加和区间取 \min 会带来 O(q \log n) 的势能(有这么多个不完全包含的点),初始有 O(n) 的势能,所以复杂度为 O(n \log n + q \log ^ 2 n)。
KTT:设两个候选线段为 a_x,b_x,目前最优线段为 c_x,令 \sum_x = ([k_{c_x} < k_{a_x}] + [k_{c_x} < k_{b_x}]) (\log n - \log sz_x)。
这里写 \log n - \log sz_x 而不是 d_x 是为了无缝搬到平衡树的证明。
考虑某次对于节点 x,和它的父亲 p 的更新,因为 x 被更新,所以 x 的势能一定下降了 \log n - \log sz_x。
从而总势能至少减少 $O(1)$。
每次更新至多带来 $O(\log n)$ 的代价取搜索。
初始势能 $O(n \log n)$。
区间修改至多让势能增加 $O(\log^2 n)$。
所以总复杂度 $O(n \log ^2 n + q \log^ 3 n)$。
区间加区间除:令 $\sum_x \log (mx_x - mn_x)$ 为势能,每次暴力遍历一个节点至少下降 $O(1)$ 的势能,初始势能 $O(\log v)$,区间修改至多让势能增加 $O(\log n \log v)$,从而总复杂度 $O(n \log v + q \log n \log v)$。
区间加区间开根:令 $\sum_x \log \log (mx_x - mn_x)$ 为势能,每次暴力遍历一个节点至少下降 $O(1)$ 的势能,初始势能 $O(\log \log v)$,
区间修改至多让势能增加 $O(\log n \log \log v)$,从而总复杂度 $O(n \log \log v + q \log n \log \log v)$。
### 势能平衡树复杂度证明
首先,势能平衡树不能使用 splay。
其次,剩下的证明一模一样,唯一区别就是区间修改导致的 $O(\log n)$ 个不完全包含的节点变成了 $O(\log n)$ 次点维护的子树变化,分析仍然不变。
对于大部分(指我知道的全部)线段树的势能分析,都可以使用同样的证明,因为一般情况下,点维护的子树变化后就只能按照最大势能分析,区间被部分包含时也只能按照最大势能分析。
实现差不多,也是满足同样的条件之后同样的暴力递归。
作用就是可以放到 LCT,静态 top tree 或者可以支持区间翻转。
于是问题 1,2 就解决了。
:::info[为何无法使用 splay]
如果你暴力递归结束,为了保证 splay 的复杂度正确,必须旋转,而这又会带来势能,从而实现势能下降到势能上升,势能上升到势能下降的循环,导致复杂度崩溃。
:::
因为 FHQ LCT 需要一些手法,所以给出[一份代码](https://www.luogu.com.cn/paste/dl344brj)。
可以看[这篇](https://www.luogu.com.cn/article/akx6once),[那篇](https://www.luogu.me/article/5m7dstf0),[这个](https://zhuanlan.zhihu.com/p/30704955),[那个](https://zx2003.blog.uoj.ac/blog/7884)去学习一下非 splay LCT。
这个东西之前为啥无人提出我也不知道。
可能是 YNOI 出的分块太多导致的。
### 单侧递归平衡树
跟单侧递归线段树差不多,只不过放到平衡树上。
这个的复杂度分析都不用分析,显然是对的。
依旧可以放到 LCT,静态 top tree 或者可以支持区间翻转。
于是问题 3 就解决了。
### 吉司机单侧递归
这个就是解决问题 4,我们在吉司机线段树上加入单侧递归的 push\_up,就做完了。
当然,我还有单侧递归 KTT ,吉司机 KTT 之类的存货,但是感觉 0 人想要。
依旧可以放到 LCT,静态 top tree 或者可以支持区间翻转。
### 优化建图
平衡树优化建图需要做一个类似可持久化的操作,在点维护的子树发生变化时新建一个点,连向新的左右儿子。
然后你还是做完了。
问题 5 就是一个静态 top tree 优化建图 + [经典好题](https://www.luogu.com.cn/problem/P8498)。
依旧可以放到 LCT,静态 top tree,但是区间翻转的优化建图没有啥意义。