专栏文章

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

mmrsrz珂愛
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min89yk6
此快照首次捕获于
2025/12/01 22:11
3 个月前
此快照最后确认于
2025/12/01 22:11
3 个月前
查看原文
前置知识：轻重链剖分、序列分块。

简介

考虑一些不能使用 polylog 数据结构维护的树上的路径修改、查询问题。
一个朴素的解决方法为直接对树的 dfs 序序列分块，然后将路径划分为 O(log⁡n)O(\log n) 个连续的区间进行修改、查询（以下统称为操作）。该方法的时间复杂度通常会额外附带 O(log⁡n)O(\log n) 或者 O(log⁡n)O(\sqrt{\log n})。

优化

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

时间复杂度分析

设点 uu 所在的重链的链长为 LL，uu 所在重链链顶的子树大小为 SS，则显然有 L≤SL\le S。
一条路径可以拆分为两条自底向上的路径，故只需考虑任意结点到根的路径操作的时间复杂度。考虑按顺序写出路径经过的每条重链的链长 L1,L2,⋯ ,LmL_1,L_2,\cdots,L_m 和对应的子树大小 S1,S2,⋯ ,SmS_1,S_2,\cdots,S_m（Sm=nS_m=n），则单次操作的时间复杂度为：
O(L1)+O(L2)+⋯+O(Lm)≤O(S1)+O(S2)+⋯+O(Sm)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)
根据轻重链剖分的性质，如果 vv 是 uu 的轻子树，则有 su>2⋅svs_u > 2\cdot s_v，其中 su,svs_u,s_v 分别为两个结点的子树大小。据此可得 2⋅Si<Si+12\cdot S_i< S_{i+1}，i=1,2,⋯ ,m−1i=1,2,\cdots,m-1。
那么有：
O(L1)+O(L2)+⋯+O(Lm)≤O(S1)+O(S2)+⋯+O(Sm)<O(n)+O(n2)+⋯+O(n2m−1)≤O(n+n2+n4+⋯ )=O(n)\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(n)O(\sqrt n)。

注意事项

块的个数是 O(n)O(n)，可以构造一个度数为 n−1n-1 的结点卡满（俗称“菊花图”）。
因此该方法对子树的修改、查询支持较差。
对于部分问题，若只含有子树查询，则可以用以下方法解决：
  • 考虑查询子树 uu。发现除了 uu 所在重链外，子树内恰好包含若干条完整的重链，且其 dfs 序连续。
  • 对 uu 所在重链进行链上的修改。
  • 对每条重链维护重链的整体信息，并使用线段树等数据结构维护。对 uu 子树包含的其他重链部分，直接在线段树上查询。
若只含有子树修改，则可类似的对重链维护“懒标记”进行延迟修改。
使用该方法需要维护的信息比较简单或具有某些性质。

例题

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...