Heavy-Light Decomposition (HLD) – Efficient Tree Path Queries

Heavy-light decomposition (HLD) decomposes a tree into O(log n) paths so path queries become O(log² n) segment tree walks.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Compute subtree sizes, heavy child, head/top chains; map nodes to array positions; segment tree on that array.

Try this in Python

# HLD sketch: pos[u] = index in base array; head[u] = chain head
# Path query: while head[u] != head[v]: query segtree between pos[head[u]] and pos[u]
print("HLD reduces tree path to few segment intervals")

Common mistakes

• Forgetting to query/upate both chains when path crosses LCA.
• Wrong DFS order for position array.

Key takeaways

• Start with “path sum on tree” template.
• Pair HLD array with segment tree for sum/max on path.