Zirnc's Blog
Recent content on Zirnc's Blog
马上订阅 Zirnc's Blog RSS 更新: https://blog.chungzh.cn/index.xml
树链剖分笔记
树链剖分（本文仅介绍 重链剖分（Heavy-Light Decomposition））的用途：
- 更新树上两点之间的路径上的所有点的值
- 求树上两点之间的路径上的最大值、最小值、和（或任意满足结合律的运算）
思想
树链剖分即把整棵树剖分成若干条链，然后用线段树等数据结构来维护链上的信息。重链剖分可以将树上的任何一条路径划分成不超过 $O(\log n)$ 条连续的链。
定义：
- 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
- 轻子节点 表示剩余的所有子结点。
- 从这个结点到重子节点的边为 重边。
- 到其他轻子节点的边为 轻边。
- 若干条首尾衔接的重边构成 重链。
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。
性质
-
树上每个节点都属于且仅属于一条重链。
-
重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。
-
所有的重链将整棵树 完全剖分。
-
在剖分时 重边优先遍历，最后树的 DFN 序上，重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链。
-
一颗子树内的 DFN 序是连续的。
-
可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。
-
因此，对于树上的任意一条路径，把它拆分成从 $lca$ 分别向两边往下走，分别最多走 $O(\log n)$ 次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$ 条重链。
实现
模板 RECORD。
定义：
- $fa(x)$ 表示节点 $x$ 在树上的父亲。
- $dep(x)$ 表示节点 $x$ 在树上的深度。
- $siz(x)$ 表示节点 $x$ 的子树的节点个数。
- $son(x)$ 表示节点 $x$ 的 重儿子。
- $top(x)$ 表示节点 $x$ 所在 重链 的顶部节点（深度最小）。
- $dfn(x)$ 表示节点 $x$ 的 DFS 序，也是其在线段树中的编号。
- $rnk(x)$ 表示 DFS 序所对应的节点编号，有 $rnk(dfn(x))=x$。
需要用两次 DFS 求出以上的所有值。
|
|