树中任意两个顶点之间有唯一的简单路径,但这条路径在遍历顺序中未必是一个连续区间。重链剖分通过安排树的顺序,使每条路径都能分成至多对数个区间,然后可以用普通的区间查询结构处理各段。
剖分本身不计算和,也不维护线段树;它的作用是保证树上路径能被正确地划分成少量区间。我们将证明段数为什么少,构造各顶点的位置,并处理点权和边权的边界差异。下面实现返回的区间适合求和等交换式聚合;区间输出顺序并不是原路径的遍历顺序。
按子树大小选择重儿子
定义 13.1.1
(有根子树大小、重边与链头)
将无向树以 为根。用 表示以 为根的子树中的顶点数,包含 本身。对于每个非叶顶点,选一个子树最大的儿子作为重儿子;本节遇到并列时选择顶点编号较小者。
通往该儿子的边称为重边,通往其余儿子的边称为轻边。沿重边向下延伸的极大连续段构成重链。每个顶点恰好属于一条链,其首顶点称为链头。根是链头,其他每个链头都是其父节点的轻儿子。
常见错误
(“重”指子树大小)
这里的“重”指所选子树的大小,与输入边权、顶点深度或直接儿子数无关。构造剖分不需要数值权重。
定理 13.1.2
(轻边数目的上界)
若 是 的轻子顶点,则 。因此每条由根出发的路径至多含 条轻边,两个顶点之间的每条路径至多经过 条重链。
证明
(沿轻边使子树大小减半)
设 是 的轻儿子, 是选中的重儿子。由于 ,
子树大小始终为正,因此从根到任一顶点的路径至多包含 条轻边。沿一条重链可以经过很多顶点,但跨越轻边会使子树大小按几何比例缩小。
任意两点路径在最低公共祖先处分成两段,而这两段分别是根路径的一部分。因此它至多跨越 条轻边,经过至多 个重链段。
证明透视
唯一需要最大子顶点的不等式
选取最大的子顶点只用在一处,即不等式 。其余都是计数:子树大小是正整数,每经过一条轻边就减少一半以上,而一条路径由两段根路径组成。重边从不进入计数,所以长链无伤大雅。任意选一个偏好的子顶点就会破坏这个不等式:若 的顶点 有大小为 和 的两个子顶点,而偏好的是大小为 的那个,则轻子顶点的大小 ,减半论证便失效。
选择最大子树的儿子才保证这个界。任意指定优先儿子,未必能让其余子树都小于父子树的一半。这些常数是上界,并非说每条路径都会使用那么多段。
先访问重儿子以构造区间
按前序遍历分配位置:先访问顶点,再访问重儿子子树,最后访问轻儿子子树。保存 pos[v]、head[v]、parent[v]、depth[v],以及反向数组 vertices[position]。
定理 13.1.3
(链与子树的连续性)
按前序遍历分配位置:先访问顶点,再访问其重子顶点的子树,最后访问各轻子顶点的子树。则重链上相邻的顶点得到连续递增的位置,而 的子树恰好占用位置 。
证明
(先走完子树再离开)
由此得到两个区间性质。第一,一条重链上相邻的顶点获得连续递增的位置:重儿子紧跟父节点被访问,这一过程持续到链尾。第二,每棵子树都是连续的,因为遍历离开子树之前会完成整个子树。其左闭右开区间为
这两个性质有关但不同。普通前序遍历已能保证子树连续;优先访问重儿子又保证重链连续。任意两点路径仍不一定是一个区间。
上述子树区间包含顶点 。若边值存于其较深端点,而查询只统计完全位于该子树内部的边,则应改用 ,排除 与父节点之间的入边。
例题 13.1.4
(七顶点有根树中的三条链)
以 0 为根,边为 。实现中轻儿子的栈顺序得到以下布局:
| 顶点 | 子树大小 | 重儿子 | 链头 | 位置 |
|---|---|---|---|---|
| 无 | ||||
| 无 | ||||
| 无 |
按位置反查的顶点顺序为 。三条链是 、 和 。顶点 1 的子树对应区间 ,含顶点 ;顶点 2 的子树对应 ,含顶点 。
根的两个儿子子树大小均为三,故按并列规则选 1 为重儿子。顶点 1 的两个叶儿子并列,选 3。其他有效的并列处理或轻子树访问顺序可能改变位置,但不会改变上述保证。
移除链头更深的一侧,而非端点更深的一侧
对于当前端点 ,如果链头不同,选择链头更深的端点。假设选中 ,输出区间 [pos[head[u]], pos[u]+1),并将 替换为 parent[head[u]]。重复直到两端链头相同。剩余路径就是两者位置之间的一个区间,包含两个端点。
定理 13.1.5
(移除链头操作的正确性)
设 是链头不同的当前端点,并设 的链头不比另一个链头浅。则从 到 的链段位于路径上,且严格在 LCA 之下,而剩下的路径是从 到 。当链头相同时,两端点在同一条链上之间的顶点构成最后一段,其较浅端点就是 LCA。因此输出的区间划分了路径上的顶点,每个顶点恰好计算一次。
证明
(每段被移除的链段都在 LCA 之下)
链头不同时,被选中的较深链头必定严格位于当前最低公共祖先之下。否则若该祖先位于所选链段上,另一端点必须经过另一条轻儿子边界向下,其链头会更深,与选择规则矛盾。
因此,从所选端点向上到其链头的整段都位于路径上且在最低公共祖先之下。移除该段后从链头的父节点继续,留下的是更短的路径,不会再次计入已移除的顶点。连接链头和父节点的边是轻边,因为所选链头不是根链头。
当两个端点同属一条链时,剩余路径上的顶点都在该链上,其中较浅的端点就是它们的最低公共祖先。包含最后一个区间便得到所有路径顶点的互不重叠划分,最低公共祖先恰好计入一次。轻边数量界限制了输出段数。
证明透视
为什么由链头深度而非端点深度决定
唯一不寻常的事实是较深的链头严格在 LCA 之下。若 LCA 在被选的链上,另一个端点要么经由轻边挂在它下面,要么就在同一条链上;前一种情形使该端点的链头严格比被选者深,后一种情形与链头不同相矛盾。链头深度相同时,任选一个端点都可以,因为两条链都不可能含有 LCA。每次移除都使路径变短,所以循环会结束;而 LCA 只出现在最后一段,这就是边模式只调整最后一段的原因。
反例模式
端点深度相同不能让我们任意选择链
例子中的顶点 3 和 4 深度均为二,但它们的链头分别是深度为零的 0 和深度为二的 4。若移除从 3 到链头 0 的链段,会错误地包含不在路径 上的顶点 0。
比较链头深度:先移除只有顶点 4 的链,再用同链区间处理从 1 到 3 的部分。仅凭端点深度不能证明整条链位于最低公共祖先之下。
跟踪路径区间并计算静态和
例题 13.1.6
(从 4 到 6 的路径及其静态总和)
对于路径 ,区间生成过程输出:
| 当前端点 | 选中的顶点 | 左闭右开位置区间 | 下一组端点 |
|---|---|---|---|
| 结束 |
真实路径顺序是 。这些区间划分了路径顶点,但输出顺序不同。若顶点 的值为 ,展开数组为 ,路径和为 。
对于静态值数组 base,构造 prefix[0] = 0 和 prefix[i+1] = prefix[i] + base[i]。每段贡献 prefix[right] - prefix[left]。因此,本节即使不实现线段树,也可以使用剖分完成静态路径求和查询。
边权只在最后一段排除最低公共祖先的位置
定义 13.1.7
(存于较深端点的边值)
将边权存放在有根树中该边较深的端点处;根没有入边,可以存零。这样,路径上的边权对应于路径上除最低公共祖先之外的顶点:其余每个路径顶点都代表一条通往父节点且位于路径上的边。
每个非最后区间仍必须包含其链头:链头与父节点之间的边正是正在跨越的轻边。只有最后一个同链区间需要改变,将左端点向前移动一位以排除最低公共祖先。若 ,边路径为空,不输出最后区间;点路径则含这一个顶点。
反例模式
去掉每个链头会漏掉真正的轻边
设树的根为 0,叶儿子为 1 和 2,且 1 是重儿子。顶点 2 单独构成一条轻链。从 0 到 2 的边路径包含存储在顶点 2 处的那条边。
如果边权模式排除每个区间的链头,就会删去这个单顶点区间的全部贡献,即使边权非零也会返回零。只应在最后一段排除最低公共祖先;其他链头代表路径所需的边。
例题 13.1.8
(从 4 到 3 的点路径与边路径)
在七顶点例子中,路径 的点权区间为 和 。若顶点权为 ,其和为 。若每条边在非根的较深端点 处存储值 ,边权区间则为 和 ,和为 。被排除的位置属于最低公共祖先顶点 1。
迭代构造与路径区间划分
输入的顶点编号为整数、边为端点对,这是类型和形状的前提。构造过程检查正的顶点数、合法根与端点、边数、自环、环以及连通性。重儿子并列时选较小编号;轻子树的访问顺序由输入边的入栈顺序决定。返回的布局在各次查询之间不能被修改。
def heavy_light(n, edges, root=0):
edges = tuple(edges)
if n < 1 or not 0 <= root < n or len(edges) != n - 1:
raise ValueError("a valid root and n-1 tree edges are required")
adjacency = [[] for _ in range(n)]
for u, v in edges:
if not 0 <= u < n or not 0 <= v < n or u == v:
raise ValueError("tree endpoints must be valid and distinct")
adjacency[u].append(v)
adjacency[v].append(u)
parent = [-1] * n
depth = [0] * n
parent[root] = root
stack = [root]
order = []
while stack:
u = stack.pop()
order.append(u)
for v in adjacency[u]:
if v == parent[u]:
continue
if parent[v] != -1:
raise ValueError("edges must form a tree")
parent[v] = u
depth[v] = depth[u] + 1
stack.append(v)
if len(order) != n:
raise ValueError("the tree must be connected")
size = [1] * n
heavy = [-1] * n
for u in reversed(order):
for v in adjacency[u]:
if parent[v] != u:
continue
size[u] += size[v]
h = heavy[u]
if h == -1 or size[v] > size[h] or (size[v] == size[h] and v < h):
heavy[u] = v
head = [-1] * n
position = [-1] * n
vertices = []
stack = [(root, root)]
while stack:
u, chain_head = stack.pop()
head[u] = chain_head
position[u] = len(vertices)
vertices.append(u)
for v in adjacency[u]:
if parent[v] == u and v != heavy[u]:
stack.append((v, v))
if heavy[u] != -1:
stack.append((heavy[u], chain_head))
return {"parent": parent, "depth": depth, "size": size,
"heavy": heavy, "head": head, "pos": position, "vertices": vertices}
def path_intervals(layout, u, v, edge_mode=False):
parent, depth = layout["parent"], layout["depth"]
head, position = layout["head"], layout["pos"]
n = len(parent)
if not 0 <= u < n or not 0 <= v < n:
raise ValueError("path endpoints must be valid vertices")
result = []
while head[u] != head[v]:
if depth[head[u]] < depth[head[v]]:
u, v = v, u
result.append((position[head[u]], position[u] + 1))
u = parent[head[u]]
if position[u] > position[v]:
u, v = v, u
left = position[u] + int(edge_mode)
right = position[v] + 1
if left < right:
result.append((left, right))
return result
使用 layout = heavy_light(7, [(0,1),(0,2),(1,3),(1,4),(2,5),(5,6)]),则 path_intervals(layout, 4, 6) 返回 [(3,4),(4,7),(0,2)]。构造 base = [vertex+1 for vertex in layout["vertices"]],求出前缀和,再对返回的每个区间求和,得到 24。传入 edge_mode=True 会应用上述最后区间边界规则;它不会改变输入值数组的存储方式。
说明区间结构的代价与顺序假设
命题 13.1.9
(重链剖分路径查询的开销)
建立剖分需时 、占用 空间,而一次路径查询至多分成 个区间。若一次区间查询需时 ,则路径聚合需时 ,每段另加常数工作。
证明
(计算区间数与后端调用次数)
构造时每条树边只被扫描常数次,因此需要 时间和空间。当 时,查询划分器返回 个区间;单顶点树的输出大小为常数。若单个区间查询需要时间 ,除各段常数时间合并外,路径聚合需要 时间。
静态前缀和给出 ,因此路径求和为 。支持单点更新的线段树若区间查询为 ,则路径查询为 ,单点更新为 。子树查询只需一个连续区间。值改变后,必须重建或替换前缀和;剖分本身不会维护它们。改变树的拓扑也需要另行处理或重建。
常见错误
(结合律并不允许改变次序)
输出区间适用于不依赖顺序的交换式组合,例如求和、最小值和最大值;需要配合合适的区间结构,并在必要时为路径为空选择单位元。仅有结合律不足以忽略顺序。例如,按输出区间的正向顺序拼接路径 的顶点编号会得到 425601,而实际路径顺序是 410256。有序乘积需要记录区间方向、分别累积两端的结果,并支持正向和反向区间聚合。上面的代码没有实现这一扩展。
练习与详解
快速检查
(1. 证明轻边使规模缩小,而不只依赖名称)
若 c 是 p 的轻儿子,h 是选中的最大子树重儿子,为什么 c 的子树不足 p 的一半?根路径上的轻边数量由什么限制?
解答 · 解答 1
因为 ,所以 ,即 。正整数子树大小从 出发,不可能连续超过对数次减半。因此根路径上至多有 条轻边。
快速检查
(2. 从区间集合还原例题路径)
对于从 4 到 6 的路径,列出输出的三个区间及其顶点。它们是否按路径遍历顺序输出?若顶点 v 的值为 v 加一,其和是多少?
解答 · 解答 2
区间为 (顶点 4)、(顶点 )和 (顶点 )。它们划分路径,但不是遍历顺序 。三段的和分别为 5、16 和 3,总和为 24。
快速检查
(3. 端点深度相同时比较链头)
为什么从 3 到 4 的路径必须先移除顶点 4 所在的链,不能因端点深度相等就任意选择?错误选择会包含哪个多余顶点?
解答 · 解答 3
两个链头的深度分别为零和二。深度更大的链头 4 位于最低公共祖先 1 之下,可以安全移除。如果取从 3 到链头 0 的整段,就会包含路径 之外的顶点 0。应比较链头深度,而非端点深度。
快速检查
(4. 边权模式下排除正确的顶点)
在例题树中,从 4 到 3 的路径从点权区间改成边权区间时有什么变化?为什么必须保留非最后一段的轻链链头?从一个顶点到自身的边查询包含什么?
解答 · 解答 4
点权区间为 和 ;边权区间为 和 ,只在最后一段排除最低公共祖先 1。非最后一段的链头存储其入轻边,而该边位于路径上。两端相同的边查询没有边,返回空区间列表。
快速检查
(5. 将子树区间与所选查询结构联系起来)
给出顶点 1 的子树区间。如果一个区间查询结构需要对数时间,子树查询与一般路径查询的代价分别是多少?静态前缀和能否在不进一步维护的情况下处理单点变化?
解答 · 解答 5
子树区间是 ,含 。一次区间查询需 ,一般路径需要 段,因此需 。值变化后静态前缀和会过期,必须重建或换用支持更新的结构。
快速检查
(6. 不能用结合律替代路径顺序)
为什么按输出区间的正向顺序直接拼接编号,不能得到从 4 到 6 的路径?给出两个字符串,并指出有序路径聚合需要哪些额外信息。
解答 · 解答 6
输出顺序得到 425601,真实路径得到 410256。拼接满足结合律,却依赖顺序。正确的扩展必须保留各段方向和两端各段的相对顺序,并使用有序累积及区间的正向、反向信息。本节的无序区间列表足以处理所述交换式聚合。