玩转树剖

· · 个人记录

本文中涉及的题目都不知道是否有原题。

本文并不需要熟知涉及的各种树形结构，不了解的东西搜一下它的增量法构造过程即可。

我们来康一道题：

动态失配树上链加子树加链求和子树求和。

注：失配树指造 \text{KMP} 的 nxt 构造出的树，动态失配树指动态末尾加字符的 \text{KMP} 的 nxt 构造出的树。

很显然要动态维护失配树，并且这个失配树还有加点的操作，我们可以想到什么？\text{LCT}！

但显然 \text{LCT} 无法做到子树修改操作，用 \text{Top Tree} 未免过于大材小用了，怎么搞才好呢？

如果没有动态，那么我们肯定会首选树剖。那么我们是否可以通过对树剖魔改使它能完成这些操作呢？

规定：点 x 到树根的路径为 d(x)。

首先考虑如果加入一个点，那么整棵树的轻重链划分会有什么变化呢？很显然子树大小只增不减，那么 d(x) 上的重边不可能变成轻边，所以我们可以遇到重链可以直接跳到顶。轻边可能变成重边，所以每次跳到重链顶时判断一下轻边是否变成重边即可。

轻重链的改动需要 size 进行判断。考虑每个点的 size 的变化：不难发现只有 d(x) 上的点的 size 会 +1，对应的是链加。那么我们不选择直接记录每个点的 size，而是需要用的时候就查询。

我们回顾原始树剖如何同时维护链操作和子树操作：同一重链的 dfn 是连续的，同一子树的 dfn 也是连续的。那么魔改树剖也要满足。因为时间上的考虑，我们不可能更改重链后再 dfs 一次确认新的 dfn。我们需要更高效的做法。

因为同一子树的 dfn 是连续的，那么更改重边其实就是新重边的子树的 dfn 全部减小到与重链上的 dfn 连续，把原重边的 dfn 增大。这个操作可以看做是把某一段区间向前平移，不难想到用文艺平衡树进行维护。因为每个点的 dfn 可能会有大幅度变化，我们不选择直接记录 x 的 dfn，而是需要用的时候查询 x 在文艺平衡树里面的排名。

不难发现这时候 \sout{son} 其实就没用了。

我们还需要维护每个点的 top,dep,fa。不难发现 top 的改变就相当于链覆盖，dep,fa 只有新加入的点才改变，那么这两个量很容易进行维护。

我们考虑时复。插入点时总共跳 O(\log n) 次重链，每次跳重链时要用 O(\log n) 查询 top,dfn,size 等信息，那么插入时复为 O(\log^2 n)，链修改与查询的时复不变，为 O(\log^2 n)，子树修改与查询的时复也不变，为 O(\log^2 n)。空复显然不变，为 O(n)。那么我们就使用魔改树剖完成了这题。

我们再看一题：

动态析合树上链加子树加链求和子树求和。

这题比上一题强主要是它的合并不是把点合并到树上，而是把树 A 合并到树 B 上。我们思考能否套用前一题的方法：

首先不难发现 A 中的剖分情况其实不会改变，只有 B 的剖分情况会更改。更改情况其实和加入一个点几乎一致，所以可以直接套用。

不同的是 d(x) 上的点的 size 会加 size(A)；A 上的 dep 都会改变，相当于子树加。这两个都不难解决。

我们接着看一题：

动态笛卡尔树上链加子树加链求和子树求和。

这题有边的删除，但是删除边的时复并不能保证（可能吧），那是不是就不能做了？

我们开动脑筋，发现如果用整体法看整个笛卡尔树，其实 size 还是只增不减的。那么我们不要一步一步做删边加边，而是整体解决。首先剥离出要删除的子树 A，合并到新加入的点上形成树 B，再把 B 合并到原树 C 上。显然 size(B)>size(A)，所以 C 上只有轻边可能变成重边，可以直接套用。细节较多。

我们最后看一题：

动态后缀树上链加子树加链求和子树求和。

其实和上一题差不多，分析分析就行了，读者自解不难。

最后分析一下优缺点：

优点：可以避免写 \sout\text{Top Tree}；成功把部分 \sout {10} 级算法的题目转换成为 \sout 8 级算法。

缺点：代码难写，局限性极高，时复 \log^2。

总结：屁用没有，纯属图一乐。 虽然局限性高但是却在维护特殊数据结构/树形结构上有点用，毕竟它们本身就有比较好的性质满足维护。如果使用非均摊时复的文艺平衡树就可能可以实现可持久化？ 空间爆炸！