树链剖分(Heavy-Light Decomposition)

树链剖分是一种把树上路径问题转化为序列区间问题的经典技术。它按子树大小把每个节点的一条边标为重边,其余为轻边,使得任意根到叶的路径最多跨越对数条轻边,从而把两点间路径拆成对数条连续的重链区间。

概述

树链剖分中最常用的是重链剖分。它先通过一次遍历求出每个节点的子树大小,再让每个节点指向子树最大的孩子作为重儿子,由重边串起的极长路径即重链。对整棵树做深度优先遍历时优先走重儿子,可让每条重链对应一段连续的编号区间。

核心原理

• 重轻划分:节点的重儿子是子树最大的孩子,连向它的边为重边,其余为轻边。
• 连续编号:遍历时优先访问重儿子,使同一重链上的节点获得连续的下标。
• 路径分解:两点向上跳链,每次处理链顶所在区间,总共只需对数次跳跃。
• 结合数据结构:重链上的连续区间用线段树或树状数组维护,支持区间加、区间求和、区间最值等操作。

应用场景

树链剖分广泛用于处理静态树上的路径修改与查询,如路径求和、路径最值、路径染色,以及子树整体操作。它是算法竞赛中的常用技术,也用于处理层级结构上的批量统计问题。求最近公共祖先也是它的一个自然副产品。

常见问题

问:树链剖分能处理树形态变化吗?答:标准的重链剖分针对静态树,若树需要频繁连边断边,应改用链剖树等动态树结构。

问:为什么路径最多只有对数条重链?答:因为每经过一条轻边,子树大小至少减半,而路径上轻边数量因此被对数所限,重链段数也随之为对数级。