Skip to content
Tutorials Center
My learning

Topics

Lesson 118 of 225 ยท Tries and Range Queries

Heavy-Light Decomposition

Learn heavy-light decomposition in Python: split a tree into heavy chains, map them onto an array and answer path max queries and updates in O(log^2 n).

A segment tree answers "what is the maximum between index 3 and index 9?" in O(log n). But what if your data is not a row but a tree, and the question is "what is the maximum value on the path from node u to node v?" A path in a tree is not a contiguous range of anything, so a plain segment tree cannot help directly.

Heavy-light decomposition (HLD) is the standard trick. It cuts the tree into vertical chains so that every root-to-node path crosses only O(log n) chains, and it numbers the nodes so each chain is a contiguous block of an array. A path query then becomes O(log n) range queries on a segment tree, for O(logยฒ n) per query in total. Updates stay O(log n).

Heavy and light edges

Root the tree. For every node, look at its children and find the one whose subtree is biggest. The edge to that child is the heavy edge; all other child edges are light. Following heavy edges from any node downward gives a heavy chain. Every node belongs to exactly one chain (a leaf with no heavy parent forms a chain of one).

Here is a ten-node tree. Thick arrows are heavy edges:

flowchart TD
    n0((0)) ==> n1((1))
    n0 --> n2((2))
    n1 ==> n3((3))
    n1 --> n4((4))
    n2 ==> n5((5))
    n3 ==> n6((6))
    n3 --> n7((7))
    n5 ==> n8((8))
    n5 --> n9((9))

Heavy edges (thick) form the chains 0-1-3-6, 2-5-8, and single-node chains 4, 7 and 9. The edge from a chain's top to its parent is always light.

Why only O(log n) chains per path? Go from any node up to the root. Each time you cross a light edge from a child c to its parent p, the subtree of p is at least twice the size of the subtree of c (otherwise c would have been the heavy child). So the subtree size at least doubles per light edge, and it cannot double more than logโ‚‚ n times. A path from the root to any node therefore crosses at most logโ‚‚ n light edges, so it touches at most logโ‚‚ n + 1 chains.

Step 1: sizes and heavy children

We compute subtree sizes with a loop instead of recursion, because a path-shaped tree with 100,000 nodes would exceed Python's recursion limit. Visit the nodes in an order where parents come before children (a BFS or stack order), then walk that order in reverse to add sizes into parents.

Python Subtree sizes and heavy children

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When two children tie in size, either may be heavy. The correctness proof does not care.

Step 2: chain heads and positions

Now we number the nodes so that each chain is contiguous. A DFS that visits the heavy child first does exactly this: when we start at a chain's top (its head), we walk down the heavy edges numbering pos = 0, 1, 2, ... before turning to any light child. Every node stores head[v], the top of its chain, and pos[v], its index in the array.

Doing that DFS without recursion is easiest with a loop over chain heads: pop a head from a stack, walk down its heavy chain assigning positions, and push the light children of each chain node as new heads.

Python Assign head and pos to every node

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the array order, each chain appears as an unbroken run, for example 0 1 3 6. Nodes of a subtree are also contiguous (a bonus, not needed for path queries): the subtree of v occupies positions pos[v] .. pos[v] + size[v] - 1.

Step 3: answering a path query

To query the path between u and v:

  1. While head[u] != head[v] (they are on different chains): take the one whose chain head is deeper, say u. Query the array range pos[head[u]] .. pos[u], which is the part of the path inside u's chain. Then jump to parent[head[u]].
  2. Now both are on the same chain. Query the range between pos[u] and pos[v] (smaller first). That segment contains the lowest common ancestor and the rest of the path.

Combine all results with the same operation the segment tree uses (here max). The loop jumps over at most O(log n) chains, and each jump costs one O(log n) segment tree query, which gives O(logยฒ n).

flowchart TD
    A["query(u, v)"] --> B{"head[u] == head[v]?"}
    B -- no --> C["u = the node whose head is deeper"]
    C --> D["range-query pos[head[u]] .. pos[u]"]
    D --> E["u = parent[head[u]]"]
    E --> B
    B -- yes --> F["range-query between pos[u] and pos[v]"]
    F --> G["combine all partial results"]

The query loop climbs from the deeper chain head until both nodes share a chain.

A complete implementation with updates

Below is the full structure: HLD arrays, an iterative max segment tree over positions, a point update and a path maximum query. It also checks itself against a slow walk-the-path version on a random-looking but fixed tree.

Python Path maximum with point updates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Edge values and subtree queries

Our values live on nodes. If the values live on edges, store each edge's weight on its deeper endpoint (the child). Then a path query must skip the LCA's own value: in the final same-chain step, query the range starting at pos of the shallower node plus one instead of at the shallower node itself.

Subtree queries are even easier. Because the DFS visits heavy chains in one go and each subtree stays contiguous, "all nodes in the subtree of v" is the range pos[v] .. pos[v] + size[v] - 1, a single segment tree query. That also lets you add a value to a whole subtree with a lazy segment tree.

Complexity and when to use HLD

Operation Time
Build (sizes, chains, segment tree) O(n)
Point update O(log n)
Path query (max, sum, gcd, ...) O(logยฒ n)
Subtree query O(log n)
LCA O(log n)

For plain LCA queries on a static tree, binary lifting or a sparse table over an Euler tour is simpler. HLD earns its keep when you need updates mixed with path queries, or path updates with a lazy segment tree. For an alternative divide-and-conquer approach on trees, see centroid decomposition.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How is the heavy child of a node chosen?

    The heavy child is the child whose subtree has the most nodes. That guarantees every light edge at least doubles the subtree size going up.
  2. 2. How many chains can a path from any node to the root touch?

    Each light edge on the way up at least doubles the subtree size, so there are at most log2(n) light edges and log2(n) + 1 chains.
  3. 3. What is the time complexity of a path query with a segment tree over the positions?

    At most O(log n) chains are visited, and each one needs a range query costing O(log n).
  4. 4. In the path query loop, which node do you move up?

    Moving the node whose head is deeper makes sure you never jump past the lowest common ancestor's chain.
  5. 5. Where do you store an edge's weight so HLD can query path sums over edges?

    Every non-root node has exactly one parent edge, so the child's slot can hold it. The final same-chain query then excludes the LCA's slot.

Summary

  • HLD splits a rooted tree into heavy chains: each node continues the chain through its largest child.
  • Any root path crosses O(log n) light edges, so it touches O(log n) chains.
  • A DFS that visits the heavy child first gives every chain a contiguous block in the array.
  • Path queries climb chain by chain from the deeper head; each step is one segment tree range query, for O(logยฒ n).
  • Subtrees are contiguous too, so subtree queries are a single range; the same structure gives LCA for free.
  • Edge weights go on the deeper endpoint, and the LCA's slot is skipped in the last step.

Next: Graphs