势能平衡树,单侧递归平衡树,平衡树优化建图

· · 算法·理论

问题引入

先来看几个问题:

  1. 线段树 3,but 在动态树上。
  2. 区间加、区间最大子段和,but 还支持区间翻转。
  3. 维护前缀最大值的个数,but 在动态树上。
  4. 维护前缀最大值之和,but 需要支持区间 chkmin 和区间加。
  5. 给定树上若干个点,要求这些点的点权必须大于其邻域内的点权,构造一组满足条件的方案。

势能线段树的复杂度证明

吉司机线段树:令 \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,但是区间翻转的优化建图没有啥意义。