重链剖分

重边让路径尽量留在同一条连续链上；每次不得不跨轻边时，所在子树规模至少缩小一半。于是整条树路径虽然可能穿过很多节点，却只会被切成对数个数组区间，底层区间结构再负责聚合或更新这些片段。

图示的两段路径 ​

图中根为 $1$，重链为 $1-2-4-u$ 与 $3-7-v$，另有叶子 $5$ 接在 $2$ 下、$6$ 接在 $3$ 下。重儿子优先的前序数组为

因此 $u$ 到 $v$ 的点路径，由 $[0,4)$ 的反向序列 $[u,4,2,1]$ 接上 $[5,8)$ 的正向序列 $[3,7,v]$ 组成。图中的两个区间并集说明哪些位置入选，并不规定非交换聚合的执行顺序。

同一编号还保留子树区间：$2$ 的子树是 $[1,5)$，$3$ 的子树是 $[5,9)$。链连续和子树连续能同时成立，靠的是这份具体的 DFS 访问顺序。

失效边界 ​

HLD 固定树的拓扑和根。点权或边权变化不影响分解；link/cut 改变子树大小后，重儿子选择可能在很多位置改变，应使用适合动态森林的结构，或明确支付重建成本。重链总数可以很多，受控的是单条路径跨越的轻边数。

两遍构建的确切次序 ​

第一次利用树的 DFS 遍历理路树的 Euler Tour 技巧Euler tour technique for trees用 DFS 次序把子树或树上行走线性化，并区分三种常见序列。计算 parent、depth、size 和 heavy child。第二次递归编号：

decompose(v, h):
    head[v] = h
    pos[v] = timer++
    if heavy[v] exists:
        decompose(heavy[v], h)
    for each other child c of v:
        decompose(c, c)

两遍各扫描每条树边常数次，时间为 $O(n)$。第二遍仍是完整 DFS 前序，所以 $v$ 的子树恰对应 $[pos[v],pos[v]+size[v])$；同时，在进入任何轻子树前已连续编号当前整条重链。不能把轻子树任意搬到整段遍历末尾，否则可能保留重链连续，却破坏子树区间。

有方向的路径聚合 ​

设节点值属于幺半群理路幺半群Monoid具有双侧单位元的半群。 $(M,\circ ,e)$。用线段树理路线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。在每个区间保存正向与反向两个摘要；交换两方向不是对聚合值求逆。例如矩阵乘积的逆并不等于把原矩阵次序反过来的乘积。

查询从原始 $u$ 走到原始 $v$ 时，维护 $L=R=e$：$L$ 是已经从 $u$ 端收集的前缀，$R$ 是通向 $v$ 端的后缀。链头不同时，比较它们的深度：

• 若 $u$ 侧链头较深，查询 $[pos[head[u]],pos[u]+1)$ 的反向摘要 $Q$，令 $L\leftarrow L\circ Q$，再把 $u$ 跳到链头的父节点
• 否则查询 $v$ 侧对应区间的正向摘要 $Q$，令 $R\leftarrow Q\circ R$，再把 $v$ 跳到链头父节点

会合到同一条链后，按当前 $u$ 到 $v$ 的方向取中间摘要 $Q_0$，返回 $L\circ Q_0\circ R$。结合律允许合并区间，正反摘要和两个累积器负责保持顺序；不需要交换律或逆元。求和与最大值会隐藏次序错误，字符串标签则能直接暴露它。

每次向上越过轻边，所在祖先子树至少翻倍，所以每侧最多跳 $O(\log (n+1))$ 段。若摘要占常数字、合并为常数时间，每段线段树查询为 $O(\log (n+1))$，总时间为 $O({\log }^2(n+1))$；输出展开的长字符串另计长度成本。

点权、边权与区间更新 ​

边 $(parent(v),v)$ 可存到较深端点 $v$ 的数组位置。跨链时，链头位置代表向父节点跨出的那条轻边，仍须保留；最后同链区间才排除 LCA 的位置，以免多计 LCA 上方的入边。点权则保留 LCA。两端相同时，边路径为空，返回单位元；点路径含这一个顶点。

点修改只改一个位置；路径或子树更新则交给满足相应代数条件的 lazy 区间结构。这些操作不改变拓扑，原分解仍有效。静态数据配专门的链前缀摘要等结构时，可以省去每段查询的一层对数，但应单独说明它支持哪些聚合与更新。