KACTL 算法笔记

066-图论-重链剖分

9 min read

核心概述

重链剖分（Heavy-Light Decomposition, HLD）将树分解为若干条”重链”与”轻边”，使任意两点路径可被 O(log N) 段链覆盖；结合线段树/树状数组可在 O(log² N) 内支持路径/子树查询与修改。

原文引述

Description: Heavy-Light Decomposition on trees. Decomposes any u–v path into O(log N) chains so path/subtree queries can be answered with a segment tree/fenwick over a base array. Time: Build O(N); per path op O(log² N) with a standard segment tree (can be O(log N) for some ops).

展开阐述

定义与背景

重链剖分是一种树分解技术，将树的边划分为”重边”和”轻边”两类，使任意根到节点的路径经过的轻边数量不超过 O(log N)。该技术最初用于优化树上路径查询，现已成为处理树上区间问题的标准工具。

典型适用场景：

  • 树上路径查询与修改（如路径和、路径最大值、路径异或和）
  • 子树查询与修改（利用 DFS 序的连续性）
  • 树上 LCA 查询（作为副产品）
  • 需要将树上问题转化为序列问题的场景

接口/字段/数据结构

核心数组：

  • parent[u]：节点 u 的父节点
  • depth[u]：节点 u 的深度（根为 0）
  • sz[u]：以 u 为根的子树大小
  • heavy[u]：u 的重儿子编号（若无则为 -1）
  • head[u]：u 所在重链的顶端节点
  • pos[u]：u 在线段树 base 数组中的位置（DFS 时间戳）
  • base[i]：位置 i 对应节点的权值（可选，视需求而定）

典型接口：

  • HLD(n)：构造 n 个节点的结构
  • addEdge(u, v)：添加无向边
  • init(root=0)：执行两次 DFS 完成预处理
  • lca(u, v)：返回最近公共祖先
  • queryPath(u, v)：查询路径 u→v 的聚合值
  • updatePath(u, v, val)：更新路径 u→v
  • querySubtree(u)：查询以 u 为根的子树
  • updateSubtree(u, val)：更新以 u 为根的子树

核心流程/要点

第一次 DFS（计算子树大小与重儿子）：

  1. 从根开始 DFS，计算每个节点的 sz、depth、parent
  2. 对每个节点，选择子树大小最大的儿子作为重儿子 heavy[u]
  3. 父节点到重儿子的边称为”重边”，其余为”轻边”

第二次 DFS（链分解与位置分配）：

  1. 优先沿重边递归，使同一条重链上的节点在 DFS 序中连续
  2. 为每个节点分配 pos[u]（递增的时间戳）
  3. 记录每条链的顶端 head[u]：
    • 若 u 是重儿子，则 head[u] = head[parent[u]]
    • 否则 head[u] = u（新链的起点）

路径查询/修改（u→v 路径分解）：

  1. 将 u 和 v 分别跳到所在链的顶端，每次处理较深链：
    • 设 hu = head[u], hv = head[v]
    • 若 depth[hu] < depth[hv]，交换 u、v
    • 在线段树上查询/更新区间 [pos[hu], pos[u]]
    • 令 u = parent[hu]（跳到上一条链）
  2. 当 u、v 位于同一链时（head[u] == head[v]），处理最后一段 [pos[v], pos[u]]（或 [pos[u], pos[v]]，需保证 u 更深）

子树查询/修改：

  • 由于 DFS 序的性质，以 u 为根的子树对应连续区间 [pos[u], pos[u] + sz[u] - 1]
  • 直接在线段树上对该区间进行单次操作

LCA 查询：

  • 在路径跳跃过程中，当 head[u] == head[v] 时，深度较小者即为 LCA
  • 或直接返回最后跳到同一链时深度较小的节点

复杂度与边界条件

时间复杂度：

  • 预处理（两次 DFS）：O(N)
  • 路径操作：O(log N) 段链 × O(log N) 线段树单次操作 = O(log² N)
  • 子树操作：O(log N)（单次线段树区间操作）
  • LCA 查询：O(log N)

空间复杂度：O(N) 存储数组 + O(N) 线段树

边界条件：

  • 单节点树：sz[root]=1, heavy[root]=-1, head[root]=root
  • 链状树：退化为一条重链，路径操作仍为 O(log N)
  • 完全二叉树：每层轻边数固定，保证 O(log N) 链段数
  • 森林：需为每棵树分别执行 init，或添加虚拟根节点

点权 vs 边权：

  • 点权：直接在 pos[u] 位置存储节点权值
  • 边权：将边 (parent[u], u) 的权值存储在 pos[u] 位置（较深端点）
  • 查询路径时，边权版本需注意 LCA 不计入（或根据题意调整）

实现细节与易错点

  1. DFS 顺序：第二次 DFS 必须优先访问重儿子，确保重链连续
  2. 链跳方向：始终从较深链向上跳，避免跳过 LCA
  3. 区间端点：线段树索引需与 pos 数组的基（0-based 或 1-based）保持一致
  4. 边权处理：若边权映射到子节点，路径查询的最后一段需排除 LCA（或调整查询区间）
  5. 线段树聚合方向：路径分段的聚合顺序可能影响非交换运算（如矩阵乘法），需按 u→LCA→v 的方向合并

变体与扩展

  • 带懒标记的批量更新：结合006-数据结构-懒标记线段树支持路径区间加、区间赋值
  • 可持久化重链剖分：结合主席树实现历史版本查询
  • 边权聚合：将边权映射到深度较大的端点，查询时注意 LCA 的处理
  • LCA 优化：HLD 自带 O(log N) LCA；若需 O(1) LCA 可结合011-数据结构-区间最值查询的 RMQ
  • 动态树对比：HLD 适用于静态树；若需动态连边/断边，应使用069-图论-LinkCutTree

正确性要点与不变式

重链性质不变式：

  • 从根到任意节点的路径上，轻边数量 ≤ ⌊log₂ N⌋
  • 证明：每次经过轻边，进入的子树大小 ≤ 当前子树大小的一半

链分解的完备性：

  • 每个节点恰好属于一条重链
  • 任意路径可唯一分解为若干链段的并集

DFS 序的连续性：

  • 同一重链上的节点在 pos 数组中连续排列
  • 子树节点在 pos 数组中形成连续区间

与相邻技术的对比与取舍

HLD vs 054-图论-二进制提升：

  • 二进制提升：仅支持 LCA 与祖先跳跃，复杂度 O(log N)
  • HLD：支持路径聚合/修改，复杂度 O(log² N)，功能更强

HLD vs 069-图论-LinkCutTree：

  • HLD：静态树，预处理 O(N)，操作 O(log² N)，常数小，实现简单
  • LCT：动态树（支持 link/cut），操作均摊 O(log N)，常数大，实现复杂
  • 取舍：静态树优先 HLD；动态树必须 LCT

HLD vs 068-图论-最近公共祖先的欧拉序+RMQ：

  • HLD：路径操作强大，LCA 是副产品
  • 欧拉序+RMQ：专注于 O(1) LCA 查询
  • 取舍：需要路径聚合选 HLD；仅需 LCA 且查询极多选 RMQ

HLD 与线段树的配合：

关联节点

Graph View

Backlinks