重链剖分（AI创作）

DeepSeekDoubao2025/6/1大约 14 分钟

重链剖分（AI创作）

deepseek 写

好的，我们来详细介绍一下重链剖分（Heavy-Light Decomposition, HLD） 的基本原理和具体流程。它的核心目标是将一棵树结构“扁平化”成线性序列，从而利用处理线性数据的强大数据结构（如线段树、树状数组）来高效地解决树上的路径查询和修改问题。

核心目标：
高效处理树上的路径查询（如路径和、最大值、最小值）和路径修改（如给路径上所有节点加一个值），以及子树查询/修改。时间复杂度通常能达到 O(log²n) 甚至结合高级数据结构达到 O(log n)。

基本原理：化树为链

问题根源： 树的结构是非线性的，直接查询任意两点间路径上的信息需要遍历路径上的所有节点（O(n) 时间）。对于大棵树（n 很大），这太慢了。
核心洞察： 如果能将树拆分成若干条链（Chain），并且这些链可以很好地覆盖树上的路径，那么：
- 任意一条从根到叶子的路径，都可以被拆分成 O(log n) 条连续的链片段。
- 我们可以用处理线性数据高效的数据结构（如线段树）来维护每条链上的信息。
- 查询或修改一条路径 u -> v，就转化为查询或修改 O(log n) 条链片段上的信息，再将这些结果合并。
关键策略：重链优先
- 重儿子（Heavy Son）： 对于一个节点 u，它的子节点中子树大小最大的那个子节点被称为 u 的重儿子（如果有多个大小相同，任选一个）。u 与它的重儿子之间的边称为重边（Heavy Edge）。
- 轻儿子（Light Son）： u 的其他子节点称为轻儿子。u 与轻儿子之间的边称为轻边（Light Edge）。
- 重链（Heavy Path）： 由连续的重边连接而成的路径称为一条重链。
- 轻边（Light Edge）： 连接不同重链的桥梁。
为什么能保证 O(log n) 条链？
- 关键性质： 从树根到任意一个叶子节点的路径上，遇到的轻边数量不超过 O(log n) 条。
- 证明（直观理解）： 考虑从根节点 root 走到叶子节点 leaf。
  - 每经过一条轻边 (parent -> child)，意味着 child 不是 parent 的重儿子。
  - 根据重儿子的定义，child 的子树大小 size[child] <= size[parent] / 2（因为重儿子的子树大小至少占一半）。
  - 子树大小每次经过轻边至少减半！树的大小 n 最多能减半 O(log n) 次（从 n 减到 1），所以轻边的数量最多是 O(log n)。
- 推论： 因为一条路径 u -> v 可以看作 u -> LCA(u, v) 和 LCA(u, v) -> v 两条路径的拼接，每条路径最多有 O(log n) 条轻边，那么整条路径最多被拆分成 O(log n) 段重链（因为轻边连接着重链，经过 O(log n) 条轻边就意味着要经过 O(log n) 条重链）。
线性化：DFS序与重链优先
- 为了用线段树等维护链信息，需要将树节点映射到一个线性序列（通常是DFS序）。
- HLD 的关键在于进行 DFS 时，优先遍历重儿子。
- 这样做的效果是：每条重链上的节点在 DFS 序中是连续的一段！ 这是 HLD 高效的核心原因之一。

具体流程

实现 HLD 通常需要两次 DFS（深度优先搜索）：

第一次 DFS：预处理 - 统计信息

目的： 计算每个节点必要的统计信息，为划分重链做准备。
计算内容：
- fa[u]（父节点）： 记录节点 u 的父节点。
- depth[u]（深度）： 记录节点 u 在树中的深度（根节点深度为0或1）。
- size[u]（子树大小）： 记录以节点 u 为根的子树中包含的节点数量（包括 u 自身）。这是识别重儿子的关键。
- hson[u]（重儿子）： 记录节点 u 的重儿子。初始化为 null 或 -1（表示无重儿子）。
过程：
1. 从根节点 root 开始 DFS。
2. 对于当前节点 u：
  - 初始化 size[u] = 1。
  - 遍历 u 的所有子节点 v：
    - 递归调用 DFS(v)。
    - 更新 size[u] += size[v]。
    - 如果 size[v] 大于当前记录的 size[hson[u]] 或者 hson[u] 尚未设置，则更新 hson[u] = v（选择子树最大的儿子作为重儿子）。

第二次 DFS：构建重链 - 线性化（分配DFS序）

目的： 实际划分重链，并为每个节点分配 DFS 序 (dfn[u])，标记每条重链的顶端 (top[u])。
关键点： 优先遍历重儿子！
维护变量：
- timer： 全局计数器，用于分配 DFS 序。初始为 0 或 1。
- dfn[u]： 节点 u 在 DFS 序中的位置（时间戳）。
- rnk[idx]： DFS 序位置 idx 对应的节点编号（rnk[dfn[u]] = u），通常用于线段树等数据结构。
- top[u]： 节点 u 所在重链的顶端节点（深度最小的那个节点）。根节点的 top[root] = root。
过程：
1. 从根节点 root 开始 DFS。传入两个参数：当前节点 u 和当前所在重链的顶端节点 chainTop（对于根节点，chainTop = root）。
2. 为当前节点 u 分配 DFS 序：
  - dfn[u] = ++timer
  - rnk[timer] = u (如果需要)
  - 设置 top[u] = chainTop (当前节点 u 属于传入的 chainTop 这条重链)
3. 优先处理重儿子 hson[u]（如果存在）：
  - 递归调用 DFS(hson[u], chainTop)。
  - 注意：这里传入的 chainTop 保持不变！因为 u 和 hson[u] 在同一条重链上，重链的顶端还是 chainTop。
4. 处理轻儿子 v（除了重儿子以外的其他儿子）：
  - 对于每个轻儿子 v：
    - 递归调用 DFS(v, v)。
    - 注意：这里传入的 chainTop 是 v 自身！因为轻边 (u -> v) 标志着一条新重链的开始，新重链的顶端就是这个轻儿子 v。

经过这两次 DFS，我们得到了：

fa[u], depth[u]：用于 LCA 计算和路径跳转。
hson[u]：定义了树的重链结构。
dfn[u], top[u]：这是 HLD 的核心输出。
- dfn[u] 将节点映射到线性序列。
- top[u] 标识了节点 u 属于哪条重链以及这条链的顶端。
- 关键性质： 对于每条重链 top -> ... -> u -> hson[u] -> ...，链上所有节点的 dfn 值是连续的！且 top 节点具有该链上最小的 dfn 值。

核心操作：路径查询/修改 (u -> v)

利用构建好的 HLD 结构进行路径操作：

计算 LCA(u, v)： 可以使用基于 depth 和 top 的朴素跳转（HLD 本身也能高效求 LCA，但常用倍增等辅助）。
分别处理路径 (u -> LCA) 和 (v -> LCA)：
- 当 u 和 v 不在同一条重链上时（top[u] != top[v]）：
  - 比较 u 和 v 所在重链顶端 top[u] 和 top[v] 的深度。
  - 选择顶端深度更大（在树中位置更低）的那个节点（假设是 u），处理它所在的整条重链（从 u 到 top[u]）。
    - 因为 dfn[top[u]] 到 dfn[u] 是连续的，可以用线段树等高效查询/修改区间 [dfn[top[u]], dfn[u]]。
  - 然后将 u 向上“跳跃”到 top[u] 的父节点 fa[top[u]]（这相当于跳过了整条重链，并越过一条轻边到达上一条重链）。
- 当 u 和 v 在同一条重链上时（top[u] == top[v]）：
  - 此时 u 和 v 的 LCA 就是深度较小的那个。
  - 直接处理 u 和 v 之间的连续区间 [dfn[u], dfn[v]] 或 [dfn[v], dfn[u]]（取决于 depth 大小）。
合并结果： 将路径 u -> LCA 和 v -> LCA 上各个链片段操作的结果合并（查询时），或确保所有片段都被修改（修改时）。

时间复杂度分析

跳转次数： 每次从当前节点 u 跳到 fa[top[u]]，都至少越过了一条轻边。根据关键性质，从任意节点到根的路径上最多有 O(log n) 条轻边。处理 u -> LCA 和 v -> LCA 各自最多 O(log n) 次跳转。
链上操作： 每次处理一条重链片段（连续区间），使用线段树等数据结构的时间复杂度是 O(log n)。
总复杂度： O(log n) 次跳转 * O(log n) 次链操作 = O(log²n)。如果使用结合路径聚合的 Link-Cut Trees 等更高级结构，可以优化到 O(log n)，但 HLD + 线段树的 O(log²n) 在大多数场景下已经非常高效且易于实现。
子树操作： 由于 DFS 序本身满足子树连续（[dfn[u], dfn[u] + size[u] - 1]），子树查询/修改直接在线段树上操作区间即可，复杂度 O(log n)。

总结

为什么需要 HLD？ 为了高效处理树上的路径问题（查询/修改），克服树的非线性结构。
核心思想： “化树为链”。
- 基于子树大小定义重儿子/重边/重链和轻儿子/轻边。
- 利用重链优先的 DFS 保证每条重链在 DFS 序上是连续的区间。
- 利用从根到叶轻边数不超过 O(log n) 的关键性质保证效率。
实现步骤：
- 第一次 DFS： 计算父节点 fa、深度 depth、子树大小 size、重儿子 hson。
- 第二次 DFS： 优先遍历重儿子，分配 DFS 序 dfn，标记重链顶端 top。
路径操作：
- 不断让两个点沿着重链向上跳（通过 top 和 fa[top]），每次处理跳过的整条重链（利用 dfn 的连续性）。
- 当两点跳到同一条重链上时，处理最后的连续区间。
- 总共处理 O(log n) 条链片段。
效率： 结合线段树等，路径查询/修改时间复杂度 O(log²n)，子树操作 O(log n)。
应用： 树路径和、最大值、最小值、第 K 大、路径加、路径赋值、子树操作等。是解决树上复杂问题的基础工具。

简单比喻：

想象一棵大树（原树）。HLD 就像把主要的、粗壮的树枝（重链）找出来，并用绳子把它们分别紧紧地捆成笔直的一束（每条重链对应一个连续的线性区间）。那些连接不同粗壮树枝的小枝丫就是轻边。当你想从树上的一个果子（u）走到另一个果子（v）时，你不是直接爬树枝，而是：

沿着你所在的粗树枝（重链）走到这根树枝的根部（top）。
通过一个小枝丫（轻边）跳到相邻的更粗的树枝上。
重复步骤 1 和 2，直到你和目标果子站在同一根最粗的主干树枝上。
沿着这根主干树枝走到目标果子。
每次在粗树枝（重链）上行走都是笔直高效的（线段树操作），而跳跃小枝丫（轻边）的次数不会太多（O(log n) 次）。这样，整条路径就被分解成了几段高效的直路行走。

豆包写

重链剖分（Heavy-Light Decomposition）详解：从原理到流程

一、重链剖分的核心目标

在树结构中，我们经常需要处理两类问题：

路径查询/修改：例如求树上两点间所有节点的权值和，或修改两点间路径上的节点权值。
子树查询/修改：例如求某个子树内所有节点的权值和。

直接暴力遍历树的时间复杂度很高（每次操作O(n)），而重链剖分的核心目标是：将树结构转化为线性结构，从而利用线段树、树状数组等数据结构高效处理，将单次操作复杂度降至O(log²n)。

二、基本概念：从“重”到“链”

节点的大小（size）：以该节点为根的子树的节点数量。
重儿子与轻儿子：
- 对于每个节点，子节点中size最大的那个称为重儿子（若有多个，任选其一）。
- 其他子节点称为轻儿子。
重边与轻边：
- 节点到重儿子的边称为重边。
- 节点到轻儿子的边称为轻边。
重链：
- 由连续重边连接而成的路径称为重链。每条重链的顶端节点（链中深度最小的节点）称为链头。

三、核心原理：轻边的数量限制

重链剖分的高效性源于一个关键性质：
从根到任意节点的路径上，轻边的数量不超过log₂n条。

证明思路：
若一条边(u, v)是轻边，则v的子树大小size[v] ≤ size[u]/2（否则v会是u的重儿子）。从根出发，每次经过轻边时，子树大小至少减半，因此最多经过log₂n次轻边就会到达叶子节点。

四、具体流程：两步预处理+路径拆分

第一步：预处理节点信息（两次DFS）

第一次DFS（计算size、父节点、深度、重儿子）
- 输入：树的邻接表。
- 过程：
  - 递归计算每个节点的size（初始size[u]=1，遍历所有子节点v，size[u] += size[v]）。
  - 记录每个节点的父节点（parent[u]）和深度（depth[u]）。
  - 找到每个节点的重儿子（heavy_child[u]）：遍历子节点，选size最大的那个。
第二次DFS（分配DFS序、确定链头）
- 输入：第一次DFS的结果。
- 过程：
  - 用全局变量cnt记录当前DFS序，初始为1。
  - 优先递归访问重儿子，保证重链的节点在DFS序中连续。
  - 对于节点u，先处理重儿子v：
    - dfn[u] = cnt（dfn[u]为u的DFS序），cnt++。
    - top[u] = top[heavy_child[u]]（重链的链头与重儿子相同）。
  - 再递归处理所有轻儿子v：
    - dfn[v] = cnt，cnt++。
    - top[v] = v（轻儿子作为新重链的链头）。

第二步：将树路径拆分为重链区间

当需要处理树上两点u和v的路径时，需将路径拆分为若干段重链，每段对应DFS序中的连续区间，从而用线段树处理。

路径拆分步骤：
- 当top[u] != top[v]时，将深度较大的节点向上跳链：
  - 处理区间[dfn[top[u]], dfn[u]]（或[dfn[top[v]], dfn[v]]，取决于u和v的深度）。
  - u = parent[top[u]]（跳到当前重链的链头的父节点）。
- 当top[u] == top[v]时，处理区间[min(dfn[u], dfn[v]), max(dfn[u], dfn[v])]。
子树处理：
- 子树以u为根，其DFS序区间为[dfn[u], dfn[u] + size[u] - 1]，直接用线段树处理该区间即可。

五、实例演示：一棵简单树的重链剖分

以如下树结构为例（节点权值省略）：

第一次DFS结果：
- size[7]=1，size[4]=2，size[5]=1，size[2]=4，size[6]=1，size[3]=2，size[1]=7。
- 重儿子：
  - 1的重儿子是2（size=4>size=2），
  - 2的重儿子是4（size=2>size=1），
  - 4的重儿子是7（唯一子节点），
  - 3的重儿子是6（唯一子节点）。
第二次DFS的DFS序与链头：
- 遍历顺序：1→2→4→7→5→3→6
- dfn数组：dfn[1]=1，dfn[2]=2，dfn[4]=3，dfn[7]=4，dfn[5]=5，dfn[3]=6，dfn[6]=7。
- top数组：
  - top[7]=4（链头是4），
  - top[4]=4，
  - top[2]=4，
  - top[5]=5（轻儿子，链头是自己），
  - top[6]=6（轻儿子，链头是自己），
  - top[3]=6，
  - top[1]=4。
路径示例：处理路径1-3
- top[1]=4，top[3]=6，深度3>深度1：
  - 处理区间[dfn[6], dfn[3]]=[7,6]（无效，交换顺序为[6,7]）。
  - 3跳到parent[top[3]]=1。
- 此时top[1]=top[1]=4，处理区间[dfn[1], dfn[1]]=[1,1]。
- 路径拆分为两个区间：[6,7]和[1,1]，对应线段树查询这两个区间的和。

六、复杂度分析与应用场景

时间复杂度：
- 预处理：两次DFS，O(n)。
- 单次路径操作：拆分为O(logn)条重链，每条链对应线段树的O(logn)次操作，总复杂度O(log²n)。
- 子树操作：O(logn)（直接线段树区间操作）。
典型应用：
- 树上路径的求和、最值、修改（配合线段树）。
- 快速求LCA（最近公共祖先）。
- 树链查询（如动态维护树链信息）。

七、核心思想总结

重链剖分的本质是利用树的重儿子特性，将树分解为若干条连续的重链，使得任意路径最多被拆分为O(logn)条重链。通过DFS序将树转化为线性序列后，即可用线段树等数据结构高效处理区间问题，将树上问题的复杂度从O(n)优化到O(log²n)。这是一种“分而治之”思想在树结构上的经典应用。