一种在轻重链剖分结构上序列分块的方法

· · 算法·理论

前置知识：轻重链剖分、序列分块。

简介

考虑一些不能使用 polylog 数据结构维护的树上的路径修改、查询问题。

一个朴素的解决方法为直接对树的 dfs 序序列分块，然后将路径划分为 O(\log n) 个连续的区间进行修改、查询（以下统称为操作）。该方法的时间复杂度通常会额外附带 O(\log n) 或者 O(\sqrt{\log n})。

优化

考虑对每条重链分别维护。对一条长度为 L 的重链，按照块长为 \sqrt L 进行序列分块（假设整块与散块的复杂度已经平衡，且忽略常数影响。应用时需根据实际情况调整块大小）。操作时，还是先将路径划分为 O(\log n) 部分，并在对应的重链上进行操作。

时间复杂度分析

设点 u 所在的重链的链长为 L，u 所在重链链顶的子树大小为 S，则显然有 L\le S。

一条路径可以拆分为两条自底向上的路径，故只需考虑任意结点到根的路径操作的时间复杂度。考虑按顺序写出路径经过的每条重链的链长 L_1,L_2,\cdots,L_m 和对应的子树大小 S_1,S_2,\cdots,S_m（S_m=n），则单次操作的时间复杂度为：

O(\sqrt L_1)+O(\sqrt L_2)+\cdots+O(\sqrt L_m)\le O(\sqrt S_1)+O(\sqrt S_2)+\cdots+O(\sqrt S_m)

根据轻重链剖分的性质，如果 v 是 u 的轻子树，则有 s_u > 2\cdot s_v，其中 s_u,s_v 分别为两个结点的子树大小。据此可得 2\cdot S_i< S_{i+1}，i=1,2,\cdots,m-1。

那么有：

\begin{align} O(\sqrt L_1)+O(\sqrt L_2)+\cdots+O(\sqrt L_m)&\le O(\sqrt S_1)+O(\sqrt S_2)+\cdots+O(\sqrt S_m)\\ &<O\left(\sqrt{n}\right)+O\left(\sqrt{\frac{n}{2}}\right)+\cdots+O\left(\sqrt{\frac{n}{2^{m-1}}}\right)\\ &\le O\left(\sqrt{n}+\sqrt{\frac{n}{2}}+\sqrt{\frac{n}{4}}+\cdots\right)\\ &=O(\sqrt n) \end{align}

即单次操作的时间复杂度为 O(\sqrt n)。

注意事项

块的个数是 O(n)，可以构造一个度数为 n-1 的结点卡满（俗称“菊花图”）。

因此该方法对子树的修改、查询支持较差。

对于部分问题，若只含有子树查询，则可以用以下方法解决：

若只含有子树修改，则可类似的对重链维护“懒标记”进行延迟修改。

使用该方法需要维护的信息比较简单或具有某些性质。

例题