Lesson 295
Heavy-Light Decomposition
Tree Paths in O(log² n)
1:00How to decompose a tree into heavy chains so that any path query or update runs in O(log² n) using a single segment tree.
By the end, you can
- Explain why the heavy-child rule guarantees at most log n light edges on any root-to-node path.
- Compute subtree sizes and identify every heavy child and light child in a given tree.
- Describe how HLD chains are formed and why they are laid out contiguously in one array.
- Trace the `query_path` loop step by step, identifying which chain is queried at each iteration and where the LCA is found.
- State the overall O(log² n) complexity of path queries and justify it from the log n chain bound and the O(log n) segment-tree cost per chain.
- Distinguish what HLD adds over an Euler-tour segment tree (path queries) and name the class of problems it cannot solve (non-tree subgraphs).
Up next in String Algorithms, Advanced DP & Competitive Techniques
