A tree has one simple path between any two vertices, but that path need not be one contiguous interval in a traversal order. Heavy-light decomposition arranges the tree so that every path is the union of only logarithmically many intervals. An ordinary range-query structure can then answer each piece.
The decomposition does not itself calculate sums or maintain a segment tree. Its job is to justify a small, correct partition of a tree path. We will prove why the number of pieces is small, construct their positions, and handle the boundary difference between values attached to vertices and values attached to edges. The implementation returns intervals suitable for commutative aggregates such as sums; their emitted order is not a traversal of the original path.
Choose a heavy child by subtree size
Definition 13.1.1
(Rooted sizes, heavy edges and chain heads)
Root an undirected tree at . Let be the number of vertices in the subtree rooted at , including . For each nonleaf vertex, choose one child with largest subtree size as its heavy child; ties in this lesson choose the smaller vertex ID.
An edge to that child is heavy. Edges to the other children are light. Maximal downward runs of heavy edges form chains. Every vertex belongs to exactly one chain, whose first vertex is its head. The root is a head, and every other head is a light child of its parent.
Common mistake
(Heavy is about subtree size)
Heavy refers to the chosen subtree size, not an input edge weight, vertex depth or number of immediate children. No numerical weights are needed to construct the decomposition.
Theorem 13.1.2
(Light-edge bound)
If is a light child of , then . Hence every root-to-vertex path contains at most light edges, and every path between two vertices meets at most heavy chains.
Proof
(Halving subtree sizes along light edges)
Let be a light child of , and the chosen heavy child. Since ,
Subtree size stays positive, so a root-to-vertex path can contain at most light edges. Moving along a heavy chain may cover many vertices, but crossing a light edge changes the size scale geometrically.
Any two-vertex path splits at its lowest common ancestor into parts of two root paths. It therefore crosses at most light edges and meets at most heavy-chain pieces.
Proof X-ray
The one inequality that needs the largest child
The choice of a largest child is used in exactly one place, the inequality . Everything else is counting: sizes are positive integers, each light edge more than halves them, and a path consists of two root-path halves. Heavy edges never enter the count, which is why long chains are harmless. An arbitrary preferred child breaks the single inequality: if a vertex with has children of sizes and and the size- child is preferred, the light child has , and the halving argument fails.
Choosing a largest child is what gives this bound. An arbitrary preferred child need not make the other subtrees less than half as large. The constants are upper bounds, not a prediction that every path uses that many pieces.
Visit the heavy child first to create intervals
Assign positions by a preorder traversal that visits a vertex, then its heavy child's subtree, then its light children's subtrees. Store pos[v], head[v], parent[v], depth[v], and the inverse array vertices[position].
Theorem 13.1.3
(Contiguity of chains and subtrees)
Assign positions by a preorder that visits each vertex, then its heavy child's subtree, then its light children's subtrees. Then consecutive vertices of a heavy chain have consecutive increasing positions, and the subtree of occupies exactly the positions .
Proof
(Finish a subtree before leaving it)
Two interval facts follow. First, consecutive vertices of a heavy chain receive consecutive increasing positions: the heavy child is visited immediately after its parent, repeatedly until the chain ends. Second, every subtree is contiguous because the traversal completes that subtree before returning to any outside vertex. Its half-open interval is
These are related but different facts. An ordinary preorder already makes subtrees contiguous; prioritizing the heavy child additionally makes heavy chains contiguous. An arbitrary two-vertex path still need not be one interval.
The displayed subtree interval includes vertex . If edge values are stored at their deeper endpoints and the query asks only for edges wholly inside that subtree, omit 's incoming edge by using instead.
Worked example 13.1.4
(Three chains in a seven-vertex rooted tree)
Root at 0 and use edges . The implementation's light-child stack order gives the following layout:
| Vertex | Subtree size | Heavy child | Chain head | Position |
|---|---|---|---|---|
| None | ||||
| None | ||||
| None |
The inverse position order is . Chains are , and . The subtree of vertex 1 is interval , containing vertices ; the subtree of vertex 2 is , containing .
Both root children have size three, so the heavy tie chooses child 1. At vertex 1, the tie between leaf children chooses 3. Other valid tie or light-subtree orders can change positions without changing the guarantees.
Remove the deeper chain head, not the deeper endpoint
For current endpoints , if their heads differ, choose the endpoint whose chain head is deeper. Suppose it is . Emit interval [pos[head[u]], pos[u]+1) and replace by parent[head[u]]. Repeat until the heads agree. The remaining path is then one interval between their positions, including both endpoints.
Theorem 13.1.5
(Correctness of the chain-head removal)
Let be current endpoints with different chain heads, and let be an endpoint whose head is at least as deep as the other head. Then the chain segment from down to lies on the path strictly below the LCA, and the remaining path runs from to . When the heads agree, the vertices between the endpoints on their common chain form the last piece, and its shallower endpoint is the LCA. Hence the emitted intervals partition the vertices of the path, each counted once.
Proof
(Each removed segment lies below the LCA)
With distinct heads, the deeper selected head must lie strictly below the current lowest common ancestor. If the ancestor were in the selected chain segment, the other endpoint would have to lie below a different light-child boundary with a deeper head, contradicting the selection.
Thus the segment from the selected endpoint up through its head lies entirely on the path, below the LCA. Removing it and continuing from the head's parent leaves a smaller remaining path, with no removed vertex counted again. That parent edge is light because the selected head is not the root head.
When both endpoints share a chain, all remaining vertices between them lie on that chain. Its shallower endpoint is their LCA. Including that final interval finishes a disjoint partition of all path vertices and counts the LCA exactly once. The light-edge bound limits the number of emitted pieces.
Proof X-ray
Why head depth, not endpoint depth, decides
The one non-routine fact is that the deeper head lies strictly below the LCA. If the LCA were on the selected chain, the other endpoint would hang below it through a light edge or lie on the same chain; the first case gives that endpoint a head strictly deeper than the selected one, and the second contradicts the different heads. With equal head depths either endpoint may be chosen, because neither chain can contain the LCA. Each removal shortens the path, so the loop ends, and the LCA appears only in the final piece, which is why edge mode adjusts only that piece.
Counterexample mode
Equal endpoint depths do not justify an arbitrary chain choice
In the worked tree, vertices 3 and 4 both have depth two. But their chain heads are 0 at depth zero and 4 at depth two. Removing the chain from 3 up to head 0 would wrongly include vertex 0, which is not on path .
Compare head depths: remove the singleton chain at 4 first, then finish the same-chain interval from 1 to 3. Endpoint depth alone does not establish that a whole chain lies below the LCA.
Trace the path pieces and a static sum
Worked example 13.1.6
(The path from 4 to 6 and its static sum)
For path , the chunk-producing procedure emits:
| Current endpoints | Selected vertices | Half-open positions | Next endpoints |
|---|---|---|---|
| Finished |
The true path order is . The intervals partition its vertices, but are emitted in another order. With value at vertex , the flattened array is and the path sum is .
For a static sum array base, build prefix[0] = 0 and prefix[i+1] = prefix[i] + base[i]. Each chunk contributes prefix[right] - prefix[left]. Thus the decomposition already supports a complete static path-sum query without a segment-tree implementation in this note.
Edge values exclude the final LCA position only
Definition 13.1.7
(Edge values stored at deeper endpoints)
Store an edge's value at its deeper endpoint in the rooted tree; the root has no incoming edge and may store zero. A path's edge values then correspond to its vertices except its LCA, because every other path vertex represents one edge to its parent that lies on the path.
Every nonfinal chunk must still include its chain head: the head's edge to its parent is precisely the light edge being crossed. Only the final same-chain interval changes, by advancing its lower endpoint one position to exclude the LCA. If , the edge path is empty and emits no final interval, while the vertex path contains that one vertex.
Counterexample mode
Dropping every chain head loses real light edges
In a tree with root 0 and leaf children 1 and 2, let child 1 be heavy. Vertex 2 is a singleton light chain. The edge path from 0 to 2 includes the edge stored at vertex 2.
If edge mode excluded the head of every chunk, it would remove that entire singleton contribution and return zero even when the edge weight is nonzero. Exclude the LCA only from the final chunk; other heads represent required path edges.
Worked example 13.1.8
(Vertex path versus edge path from 4 to 3)
In the worked seven-vertex tree, path uses vertex chunks and . With vertex values , its sum is . For edges storing value at each nonroot child, its chunks are instead and , giving . The excluded position belongs to LCA vertex 1.
An iterative construction and interval splitter
Inputs use integer vertex IDs and pairs of endpoints, as type/shape preconditions. Construction checks the positive size, valid root/endpoints, edge count, self-loops, cycles and connectivity. Heavy ties use the smaller ID; light-subtree order follows the stack order of the supplied edges. The returned layout must not be mutated between queries.
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
Use layout = heavy_light(7, [(0,1),(0,2),(1,3),(1,4),(2,5),(5,6)]). Then path_intervals(layout, 4, 6) returns [(3,4),(4,7),(0,2)]. Build base = [vertex+1 for vertex in layout["vertices"]], form its prefix sums, and sum each returned interval to obtain 24. Passing edge_mode=True applies the final-boundary rule described above; it does not reinterpret how the input value array was stored.
State backend costs and ordering assumptions
Proposition 13.1.9
(Cost of heavy-light path queries)
Construction takes time and storage, and a path query splits into at most intervals. If one interval query costs , a path aggregate costs , apart from constant work per piece.
Proof
(Counting pieces and backend calls)
Construction scans each tree edge only a constant number of times, so it takes time and storage. The query splitter returns intervals for , with constant-size output on a one-vertex tree. If one interval query takes time , a path aggregate takes time, apart from constant per-piece combination.
Static prefix sums give and hence path sums. A point-update segment tree with range queries gives path queries and point updates. A subtree query uses its one contiguous interval. Prefix sums must be rebuilt or replaced when values change; the decomposition alone does not maintain them. Changing the tree's topology also requires a separate method or rebuilding.
Common mistake
(Associativity does not license reordering)
The emitted chunks support order-insensitive, commutative combinations such as sums, minima or maxima, using an appropriate range backend and empty-path identity when needed. Associativity alone does not justify ignoring order. For example, concatenating vertex labels in the emitted forward chunk order for gives 425601, while actual path order is 410256. Ordered products need directional intervals, separate accumulators for the two endpoint sides, and suitable forward/reverse range aggregates. The code above does not implement that extension.
Exercises and worked solutions
Quick check
(1. Prove the light-edge shrink rather than relying on the name)
If c is a light child and h a largest heavy child of p, why is the subtree at c less than half that at p? What bounds the number of light edges on a root path?
Solution · Solution 1
We have , so and . Positive integer subtree sizes cannot repeatedly halve more than logarithmically many times from size . Thus at most light edges occur on a root path.
Quick check
(2. Reconstruct the worked path from its interval sets)
For path 4 to 6, list the three emitted intervals and their vertices. Do they occur in path traversal order? Give the sum when vertex v has value v plus one.
Solution · Solution 2
The intervals are for 4, for , and for . They partition the path but are not in its traversal order . Their sums are 5, 16 and 3, totaling 24.
Quick check
(3. Compare heads when endpoints have equal depth)
Why must path 3 to 4 remove vertex 4's chain first rather than selecting either endpoint arbitrarily from their equal depths? Which unwanted vertex would the wrong choice include?
Solution · Solution 3
Their heads have depths zero and two. The deeper head at 4 lies below LCA 1 and is safe to remove. Taking the whole chain from 3 to head 0 instead would include vertex 0, outside path . Compare chain-head depth, not endpoint depth.
Quick check
(4. Exclude the right vertex in edge mode)
For path 4 to 3 in the worked tree, what changes between vertex and edge intervals? Why must a nonfinal light-chain head remain included? What does an edge query from a vertex to itself contain?
Solution · Solution 4
Vertex intervals are and ; edge intervals are and , excluding LCA 1 only in the final piece. A nonfinal head stores its incoming light edge, which is on the path. An equal-endpoint edge query has no edge and returns no intervals.
Quick check
(5. Connect one subtree interval to a chosen backend)
Give the interval for the subtree at vertex 1. With a range-query backend costing logarithmic time, compare a subtree query with a general path query. Can static prefix sums handle a point change without further maintenance?
Solution · Solution 5
The subtree interval is , containing . One backend query costs , while a general path needs pieces and thus . Static prefix sums become stale when values change; they must be rebuilt or replaced by a suitable update-capable backend.
Quick check
(6. Do not substitute associativity for path order)
Why does directly concatenating labels in the emitted forward chunk order fail for path 4 to 6? Give the two strings and identify the extra information an ordered path aggregate would require.
Solution · Solution 6
The emitted order gives 425601, while the true path gives 410256. Concatenation is associative but order-sensitive. A correct extension must retain chunk direction and the relative order of the two endpoint sides, using ordered accumulators and forward/reverse range information. The unordered chunk list is sufficient for the commutative aggregates stated in this lesson.