Heavy paths
Also known as: Heavy-light decomposition · HLD · heavy path decomposition · heavy and light edges · path queries on trees · path queries
How to answer questions about the path between two vertices of a tree, the maximum, the sum, add to all, in O(log² n). From each vertex continue the path into the largest subtree; such heavy paths cut any path in the tree into O(log n) pieces, and in the right numbering each piece is a stretch of an array.
Below is the relief of the mountains above Almaty from NASA’s satellite radar, in cells of 165 metres. For each cell it has been computed where water flows from it, and the result is a tree: each cell has one “parent”, the cell downstream, and the roots are the edges of the map, where water leaves the mountains. Each coloured stream is a heavy path: going upstream, at each fork it turns into the tributary that brings the most water. The dashed lines are the real riverbeds from OpenStreetMap. The algorithm knew nothing of rivers, yet the heavy paths fell into them by themselves. Tap any point to see where its water goes.
From Big Almaty Lake the water takes 117 steps to the edge of the mountains, and this whole way is one heavy path: 115 of its 118 cells lie within 350 metres of the bed of the Bolshaya Almatinka. From Medeu it is 53 steps along one heavy path, 52 cells of 54 by the bed of the Malaya Almatinka. And from a slope near Shymbulak, the one chosen on the map, the water passes through three heavy paths: a brook, a bigger stream, the Malaya Almatinka. The profile under the map shows why there are few transitions: at each orange point the catchment area the water is gathered from at least doubles.
Below the profile is the same way in numbers. All 28,341 cells are written out in one row in a special order, and the water’s way, however many cells it has, takes up a few solid stretches of this row. The whole catchment above the chosen cell is one stretch, the light one. This is just what is needed to ask questions about paths in a tree through a segment tree.
The idea
For each vertex of the tree choose a heavy child, the one with the most vertices in its subtree. Call the edge to it heavy, and those to the other children light. Heavy edges join into heavy paths: each vertex has at most one heavy edge down and at most one up, so these are chains, and each vertex lies on exactly one. Call the top vertex of a chain its head. In a drainage network the subtree of a cell is its catchment, and the heavy child is the tributary that brings more water. So the heavy paths here are the main riverbeds.
The path from any vertex to the root moves from one heavy path to another at most log₂ n times. Walk the tree depth first, going into the heavy child first, and number the vertices in the order of the walk: each heavy path becomes a stretch of numbers. Any path in the tree is a few such stretches, and a segment tree works on stretches.
To answer a question about the path between vertices a and b, climb from the one whose chain head is deeper: the whole piece from the head to it is a stretch of numbers; ask the segment tree about it and move to the head’s parent. When both vertices are on one chain, the last stretch between them is left. Updates are built the same way: “add x to all vertices of the path” is an addition on a few stretches.
Why there are few pieces
The path from any vertex to the root of a tree of n vertices has at most log₂ n light edges.
Let the edge from u to its parent p be light. Then p has a heavy child h ≠ u whose subtree has no fewer vertices than the subtree of u. The subtree of p includes both subtrees and p itself: size(p) ≥ 1 + 2 · size(u) > 2 · size(u). So each climb along a light edge more than doubles the subtree size. It starts at one and does not exceed n, so there are at most log₂ n light edges on the path.
In a drainage network this reads without formulas: when a brook does not continue on its own but flows into another stream, the catchment of that stream is no smaller than the brook’s, and after the confluence the area at least doubles. The largest catchment on this map, of the Bolshaya Almatinka, is 219 km², about eight thousand cells, log₂ ≈ 13, and in practice nowhere are there more than five such confluences. Hydrologists have long known a similar quantity: the Horton–Strahler stream order grows by one only when two streams of the same order meet, and so it too is at most the logarithm of the number of sources.
If a depth-first walk goes into the heavy child first, the numbers of the vertices of each heavy path are consecutive, and the numbers of the vertices of each subtree are consecutive. The path between any two vertices consists of at most 2 log₂ n + 1 stretches of numbers, and climbing by heads finds them all.
The heavy child gets its number right after its parent, because the walk goes into it first: hence the first statement. The second holds for any depth-first walk: it does not leave a subtree until it has gone through all of it.
Now the climb. Let the chain heads of a and b be different, with the head of a’s chain no higher than the head of b’s. We show that the common ancestor of a and b lies above the head of a’s chain, that is, the whole piece from the head to a is part of the path. If the common ancestor lay in the subtree of the head, it would be an ancestor of a inside that subtree, and such vertices are exactly the piece of a’s chain from the head to a. Then b would also lie in the subtree of the head, and its chain, not passing through the head of a’s chain, would start deeper, contrary to the choice. So the piece from the head to a is taken whole, and we move to the head’s parent along a light edge. Each such step uses up one light edge on the path from a or from b to the root, at most 2 log₂ n of them in all, plus one more stretch, the last, on the common chain.
On each stretch the segment tree answers in O(log n), so a question or an update on a path costs O(log² n). A question about a subtree is one stretch, O(log n). The numbering for paths and for subtrees is the same, and one segment tree answers both kinds of question.
Code
First, the drainage network. The relief is “flooded” from the edges, each time continuing from the lowest cell the water has already reached; this is how drainage is computed from relief in geoinformatics (Richard Barnes and co-authors called the method priority-flood). A cell that the flood reached from a neighbour drains into that neighbour. Then subtree sizes, heavy children and the numbering, without recursion: river trees have hundreds of levels, and general trees can have hundreds of thousands. And finally, downpours: rain in a cell adds water to all the cells downstream, and the question is the largest flow on the path along the riverbeds between two cells. Each answer is checked against a direct count.
There are 11,211 heavy paths, but almost all of them are brooks of one or two cells; the longest are 191, 150 and 145 cells. The path between two cells of one catchment is cut into 4.4 stretches of numbers on average and never more than 10, while the direct count goes over 59 cells per question on average. The difference grows with the depth of the tree: on a river of a thousand cells the direct count goes over a thousand, while there are still only a few stretches.
What it costs
| Method | Preparation | Path: question or update | Subtree |
|---|---|---|---|
| Directly, by parents | O(n) | O(path length), up to O(n) | O(subtree size) |
| Heavy paths and a segment tree | O(n) | O(log² n) | O(log n) |
| Binary lifting | O(n log n) | O(log n), but only without updates | — |
| Sleator–Tarjan dynamic trees | O(n) | O(log n) on average per operation, and the tree can be restructured | — |
A benchmark on river-like trees: each new cell flows into one of the eight previous ones, so the tree is deep, a long stream with short tributaries. Only 300 actions are measured, downpours and questions about the maximum on a path, without preparation: for heavy paths preparation is O(n), one walk.
The direct count grows as the path length, that is, linearly: on 64,000 vertices it is forty times slower than heavy paths in Python and more than ten times slower in Go. Heavy paths hardly notice the growth: the number of stretches grows as a logarithm.
Where it is easy to go wrong
- Heavy by subtree size, not by depth. If the path is continued into the deepest subtree, you get a “long path” decomposition, where there can be on the order of √n transitions. The log₂ n bound rests only on the doubling of size.
- Climb from the vertex whose head is deeper, not from the one that is deeper itself. A vertex can be deep but lie on a long chain with its head right at the root; climbing from it will jump over the common ancestor.
- Values on edges. If the question is about edges, for example the narrowest stretch of a river between points, an edge’s value is stored in its lower vertex, and on the last stretch the common ancestor is excluded: its vertex stores an edge that is not part of the path.
- Recursion. A recursive walk will crash on a chain tree of a hundred thousand vertices; a walk with a stack, as in the code, will not.
- Addition and maximum together. The segment tree needs a lazy operation: an addition that hangs on a node and is not pushed down until needed. Without it, adding on a stretch costs its length.
Where it works
In olympiads heavy paths are the standard answer to questions about tree paths with updates: add on a path, find the maximum or the sum, recolour. Without updates the lowest common ancestor and prefix sums from the root are usually enough. If the tree itself changes, with edges deleted and added, the dynamic trees of Sleator and Tarjan are needed; their analysis rests on the same light-edge bound. Heavy paths also give the lowest common ancestor without tables: climbing by heads to the common chain is O(log n) steps, and on the common chain the answer is whichever of the two vertices is higher. In drainage networks computed from relief the same decomposition picks out the main riverbeds: along them water reaches the outlet of the catchment.
History
The decomposition into heavy and light edges appeared in 1981 in the work of Daniel Sleator and Robert Tarjan on dynamic trees, a structure in which a forest can be cut and linked while answering questions about paths in logarithmic time. The bound “at most log n light edges on the way to the root” was the main tool of the analysis there. Competitive programming picked up the technique later, together with the segment tree, and it became known by the abbreviation HLD.
Problems
Downpours over real mountains: rain in a cell adds water to all the cells downstream, and the question is the largest flow on the path along the riverbeds between two cells. Among the tests are the same drainage network of the mountains above Almaty and a chain river of a hundred thousand cells, on which the direct count does not make it in time.
Flood watchData: Relief of the mountains over Almaty: NASA SRTM v3 (1″) via Open Topo Data, public domain Rivers of the mountains over Almaty © OpenStreetMap contributors, ODbL (export of 24 Oct 2026)