What is Heavy-Light Decomposition?
Learn how heavy-light decomposition splits a tree into chains for fast O(log^2 n) path queries, with steps and code.
Expected Interview Answer
Heavy-light decomposition splits a tree into vertical chains so that any root-to-node path crosses at most O(log n) chains, letting path queries (sum, max, update) run in O(log^2 n) using a segment tree over each chain.
For every node, the child with the largest subtree is marked as its 'heavy' child, and the edge to it is a heavy edge; every other child edge is 'light'. Chaining heavy edges together produces disjoint heavy paths that partition the whole tree, and each is mapped onto a contiguous range in an array so a segment tree or Fenwick tree can answer range queries on it. Moving from any node to the root crosses at most O(log n) light edges, because each light edge at least halves the subtree size, so a path query walks up chain by chain, querying each chain's segment tree once. This turns tree path problems into a bounded number of array range problems, which is why it underlies subtree/path sum, LCA, and path-update problems on large trees.
- O(log^2 n) path queries and updates on trees
- Reduces tree problems to segment-tree range problems
- At most O(log n) light-edge jumps per root path
- Foundation for LCA, path-sum, and path-max queries
AI Mentor Explanation
Think of a domestic cricket academy's coaching lineage as a tree, where each senior coach mentors several junior coaches. The academy designates one 'main successor' per coach — the junior who trains the most players — and that mentor-to-successor link is a heavy edge, chained together into a long coaching lineage. Tracing any coach's ancestry to the academy founder mostly slides along one lineage chain, only jumping to a different chain a few times, since each jump means the junior's group was less than half the size. This is why finding common coaching ancestry between two coaches only needs a handful of chain jumps, not a walk through every mentor individually.
Step-by-Step Explanation
Step 1
Compute subtree sizes
One DFS pass computes the size of every subtree rooted at each node.
Step 2
Mark heavy children
For each node, the child with the largest subtree becomes its heavy child; that edge is a heavy edge.
Step 3
Build chains and map to array positions
A second DFS follows heavy edges first, assigning each node a contiguous array index within its chain.
Step 4
Answer queries by walking chains
To query a path, repeatedly jump to the top of the current chain and query the segment tree, moving to the parent chain until both endpoints share a chain.
What Interviewer Expects
- Explain why the heavy child is the largest-subtree child
- Justify the O(log n) bound on light-edge jumps via the halving argument
- Describe mapping chains to array ranges for a segment tree
- State the overall complexity as O(log^2 n) per path query
Common Mistakes
- Forgetting to recompute heavy children after tree modifications
- Confusing heavy-light decomposition with simple binary lifting for LCA
- Not realizing chains must be contiguous in the array for segment tree range queries to work
- Underestimating implementation complexity of combining chain jumps with segment tree merges
Best Answer (HR Friendly)
“Heavy-light decomposition breaks a tree into a small number of long chains so path queries feel like array range queries. I would use it whenever I need fast repeated path sum or path max queries on a large, mostly static tree, since it caps the number of chain switches at O(log n).”
Code Example
import sys
sys.setrecursionlimit(200000)
def build_hld(n, adj, root=0):
parent = [-1] * n
size = [1] * n
heavy = [-1] * n
order = []
def dfs_size(u, p):
parent[u] = p
for v in adj[u]:
if v != p:
dfs_size(v, u)
size[u] += size[v]
if heavy[u] == -1 or size[v] > size[heavy[u]]:
heavy[u] = v
dfs_size(root, -1)
chain_head = [0] * n
pos = [0] * n
counter = [0]
def dfs_chain(u, head):
chain_head[u] = head
pos[u] = counter[0]
counter[0] += 1
order.append(u)
if heavy[u] != -1:
dfs_chain(heavy[u], head)
for v in adj[u]:
if v != parent[u] and v != heavy[u]:
dfs_chain(v, v)
dfs_chain(root, root)
return parent, chain_head, pos, order
def path_query(u, v, parent, chain_head, pos, depth, query_range):
result = 0
while chain_head[u] != chain_head[v]:
if depth[chain_head[u]] < depth[chain_head[v]]:
u, v = v, u
result += query_range(pos[chain_head[u]], pos[u])
u = parent[chain_head[u]]
if depth[u] > depth[v]:
u, v = v, u
result += query_range(pos[u], pos[v])
return resultFollow-up Questions
- How would you combine heavy-light decomposition with a Fenwick tree instead of a segment tree?
- How does heavy-light decomposition handle subtree updates as well as path updates?
- How would you support dynamic tree edits without rebuilding all chains?
- How does heavy-light decomposition compare to Euler tour techniques for LCA?
MCQ Practice
1. What determines which child of a node is its heavy child?
The heavy child is the one whose subtree has the most nodes, guaranteeing at most O(log n) light edges on any root path.
2. What is the time complexity of a single path query using heavy-light decomposition with a segment tree?
Each of the O(log n) chains crossed requires an O(log n) segment tree query, giving O(log^2 n) total.
3. Why can a root-to-node path cross at most O(log n) light edges?
A light child’s subtree is at most half the parent subtree’s size, so subtree size at least halves at each light edge, bounding the count to O(log n).
Flash Cards
What is a heavy edge in heavy-light decomposition? — The edge from a node to the child whose subtree has the most nodes.
What is the complexity of a path query with HLD and a segment tree? — O(log^2 n): O(log n) chains times O(log n) per segment tree query.
Why are chains stored as contiguous array ranges? — So a segment tree or Fenwick tree can answer range queries on each chain efficiently.
What bounds the number of light edges on a root path? — Each light edge at least halves the subtree size, giving an O(log n) bound.