Heavy–Light Decomposition

Heavy–light decomposition (often abbreviated HLD or termed heavy-path decomposition) is a structural tree-partitioning technique in computation and algorithms introduced in 1983 by Daniel D. Sleator and Robert E. Tarjan (alongside a related 1984 formulation by Dov Harel and Robert E. Tarjan for nearest common ancestors). Given an arbitrary rooted tree T of N vertices—which may be highly unbalanced, such as a degenerate caterpillar tree of depth O(N)—heavy–light decomposition classifies every tree edge as either heavy or light according to subtree sizes, partitioning the vertex set V into a family of vertex-disjoint downward paths called heavy chains.

The central mathematical guarantee of heavy–light decomposition is that any simple path from the root to a vertex v traverses at most ⌊log₂ N⌋ light edges and therefore intersects at most ⌊log₂ N⌋ + 1 heavy chains. By laying out the vertices of T in a Depth-First Search (DFS) order that visits each node's heavy child first, every heavy chain AND every rooted subtree T_u maps to a contiguous interval in a flat 1D array of length N. This linear layout reduces arbitrary associative path queries (such as path sum, path maximum, or non-commutative matrix products) and subtree updates on an arbitrary tree to O(log N) interval operations on a segment tree, yielding O(log² N) (or O(log N) with balanced chain trees) worst-case time per tree operation.

Subtree Sizes, Heavy Edges, and Light Edges

Let T = (V, E) be a rooted tree with vertex count N = |V| and root r ∈ V. For every vertex u ∈ V, let T_u denote the rooted subtree of T consisting of u and all its descendants, and define its subtree size as s(u) = |T_u|:

For each non-leaf vertex u ∈ V, select a single child c* ∈ children(u) that maximizes the subtree size s(c*) (breaking ties arbitrarily):

This choice partitions the outgoing child edges of u into two classes:

1. Heavy Edge: The single edge (u, c*) connecting u to its largest-subtree child c* (referred to as the heavy child of u). Note that in Sleator and Tarjan's alternative strict definition, an edge (u, w) is heavy if s(w) > s(u)/2; the argmax variant ensures every non-leaf vertex has a heavy child while preserving the logarithmic light-edge bound.
2. Light Edges: All remaining child edges (u, w) for w ∈ children(u) \ {c*}. Each such w is called a light child of u.

Because every vertex u has at most one heavy child and at most one parent, the subgraph of T formed by all heavy edges has maximum in-degree 1 and maximum out-degree 1, decomposing V into a disjoint union of downward paths called heavy chains (with leaves or vertices lacking a heavy child forming singleton chains if not entered from above). Each heavy chain C has a unique highest vertex called the chain head head(C), which is either the global root r or a light child of its parent.

Proof of the ⌊log₂ N⌋ Light-Edge Bound

Within computational complexity theory, the efficiency of heavy–light decomposition rests on the Subtree Halving Lemma: for any light edge (u, w) connecting a parent u to a light child w, the subtree size satisfies:

Proof: Because w is not the selected heavy child c* of u, the heavy child c* ≠ w has subtree size s(c*) ≥ s(w). Since T_w and T_c* are disjoint subtrees inside T_u (which also contains u itself), we have:

Consequently, every time a downward path from the root r to a vertex v traverses a light edge (u, w), the size of the remaining subtree is reduced by more than a factor of 2. Because s(r) = N and s(v) ≥ 1, any root-to-v path can traverse at most ⌊log₂ N⌋ light edges, and thus passes through at most ⌊log₂ N⌋ + 1 contiguous heavy-chain segments. For any two vertices u, v ∈ V with lowest common ancestor a = LCA(u, v), the unique tree path P(u, v) = P(u, a) ∪ P(a, v) partitions into at most 2⌊log₂ N⌋ + 1 contiguous intervals of heavy chains.

Dual-Pass O(N) Preprocessing and Heavy-First DFS Ordering

Heavy–light decomposition is constructed in O(N) time and O(N) space using two depth-first traversals:

1. DFS Pass 1 (Subtree Sizes, Depths, Parents, and Heavy Children): For each vertex u, record *parent*[u] and *depth*[u], compute s[u] = 1 + ∑ s[w] in post-order, and identify *heavy*[u] as the child w with maximum s[w].
2. DFS Pass 2 (Heavy-First Linearization and Chain Heads): Assign each vertex u a 1D array position *pos*[u] ∈ {0, …, N − 1} and a chain head *head*[u] in pre-order by visiting *heavy*[u] first before visiting any light children w ≠ *heavy*[u]:
   • For the heavy child c* = *heavy*[u], propagate the chain head: *head*[c*] ← *head*[u], and recurse on c* immediately so that *pos*[c*] = *pos*[u] + 1.
   • For each light child w ≠ c*, start a new heavy chain with *head*[w] ← w and recurse on w.

This heavy-first pre-order numbering satisfies two simultaneous interval invariants on the 1D array:

• Heavy-Chain Contiguity: For any vertex x and any ancestor a lying on the same heavy chain (*head*[x] = *head*[a]), the vertices on the tree path from a down to x occupy the exact contiguous array slice [*pos*[a], *pos*[x]].
• Subtree Contiguity: For every vertex u ∈ V, the entire subtree T_u occupies the exact contiguous array slice [*pos*[u], *pos*[u] + s[u] − 1].

Answering On-Line LCA and Path Queries

To evaluate an associative function ⊕ (or apply a lazy range update) along the tree path between u and v using an underlying segment tree over positions {0, …, N − 1}:

1. While *head*[u] ≠ *head*[v] (meaning u and v lie on different heavy chains):
   • Without loss of generality, assume the chain head of u is deeper than that of v: *depth*[*head*[u]] ≥ *depth*[*head*[v]].
   • Query (or update) the contiguous heavy-chain prefix [*pos*[*head*[u]], *pos*[u]] in the segment tree in O(log N) time.
   • Jump u across the light edge above its chain head: u ← *parent*[*head*[u]].
2. Once *head*[u] = *head*[v], u and v reside on the same heavy chain; the shallower of {u, v} is LCA(u, v), and one final segment-tree query on [min(*pos*[u], *pos*[v]), max(*pos*[u], *pos*[v])] completes the path evaluation.

Because the loop executes at most 2⌊log₂ N⌋ times and each segment-tree query takes O(log N) time, total path query/update time is O(log² N) (and finding LCA(u, v) alone without a segment tree takes O(log N) time with zero extra space beyond head, parent, and depth).

Comparative Performance of Tree Path and Subtree Data Structures

Furthermore, building a separate weight-balanced segment tree (or globally biased binary search tree) over each heavy chain where each vertex x is weighted by its light-child subtree sum s(x) − s(*heavy*[x]) reduces path queries from O(log² N) to O(log N) by telescoping the tree depths across light edges, and provides the static prototype for the dynamic link/cut tree (which replaces fixed heavy chains with dynamically updated preferred paths maintained via a splay tree).

1. Phylogenetic Tree Mutation Tracking and Ancestral State Reconstruction: In computational evolutionary biology, ultra-large viral phylogenies (such as SARS-CoV-2 trees with millions of sequences) use heavy–light decomposition to query mutational branch paths and aggregate clade frequencies across subtrees in logarithmic time.
2. Network Routing and Bottleneck Capacity Verification: When paired with a minimum spanning tree or a Gomory–Hu tree, heavy–light decomposition answers online bottleneck capacity queries and dynamic edge-weight updates along tree paths in O(log² N) time.
3. Hierarchical Scene Graphs and Skeletal Kinematics: Real-time physics and robotics engines decompose articulated kinematic chains via HLD to compose non-commutative 4×4 rigid-body transformation matrices from root to end-effector after joint-angle updates.

How are edge weights (rather than vertex weights) stored in a heavy–light decomposition?

In a rooted tree, every edge e = (u, v) with u = *parent*[v] corresponds uniquely to its deeper endpoint v. Assigning the weight of edge e to vertex v reduces edge-path queries between x and y to vertex-path queries excluding the lowest common ancestor a = LCA(x, y) (querying [*pos*[a] + 1, *pos*[w]] on the final shared heavy chain).

Why can't a simple Euler tour replace heavy–light decomposition for path maximum queries?

In an Euler tour (entering and exiting each subtree), a root-to-node path is represented by prefix sums in which finished sibling subtrees are added on entry and subtracted on exit. That cancellation requires an invertible group operation (such as addition or XOR); non-invertible operations like max, min, or greatest common divisor cannot cancel off-path subtrees in an Euler tour and therefore require heavy–light decomposition.

1. Sleator, D. D., & Tarjan, R. E. (1983). "A data structure for dynamic trees." Journal of Computer and System Sciences, 26(3), 362–391. https://doi.org/10.1016/0022-0000(83)90006-590006-5)
2. Harel, D., & Tarjan, R. E. (1984). "Fast algorithms for finding nearest common ancestors." SIAM Journal on Computing, 13(2), 338–355. https://doi.org/10.1137/0213024
3. Tarjan, R. E. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611970265
4. Alstrup, S., Holm, J., de Lichtenberg, K., & Thorup, M. (2005). "Maintaining information in fully dynamic trees with top trees." ACM Transactions on Algorithms, 1(2), 243–264. https://doi.org/10.1145/1103963.1103966