Heavy-Light Decomposition
You know Euler tours for subtrees. HLD handles path queries by decomposing into heavy chains.
Lessons
1. Intro
(Solving path queries fast)
2. The Path Query Problem
(Maximum on a path)
3. Why Subtree Tricks Fail
Paths cross subtree boundaries
4. The Chain Idea
(Break paths into chains)
5. Subtree Size
(Counting descendants)
6. Heavy and Light Edges
(Splitting by subtree size)
7. Heavy Paths as Chains
(Maximal heavy sequences)
8. The $O(\log n)$ Chain Property
(Why paths cross few chains)
9. Path to LCA Structure
(Two paths meet at ancestor)
10. Chain Decomposition DFS
(Assigning nodes to chains)
11. Chain Positions
(Indexing nodes within chains)
12. Chain Heads
(Top node of each chain)
13. Segment Tree per Chain
(Range queries on chains)
14. Single Segment Tree Improvement
(Flatten all chains)
15. Path Query Algorithm
(Walk up to LCA)
16. Depth Array
(Comparing node depths)
17. Parent Array
(Jumping to parent)
18. Update Operation
(Changing a node value)
19. Edge Queries vs Vertex Queries
(Where to store values)
20. LCA in HLD
(Finding the meeting point)
21. Complexity Analysis
(Time and space bounds)
22. Implementation - Preprocessing
(Computing sizes and parents)
23. Implementation - Decomposition
(Building chains)
24. Implementation - Segment Tree
(Supporting range max)
25. Implementation - Path Query
(Combining chain segments)
26. Path Updates
(Modifying all nodes on path)
27. Path Sum Queries
(Sum instead of maximum)
28. Problems - Path Queries II - Read Statement
(CSES 1138 path maximum)
29. Path Queries II - Heavy Edges
(Decompose the tree)
30. Path Queries II - Segment Tree
(Store values by position)
31. Path Queries II - Query Algorithm
(Walk up both sides)
32. Path Queries II - Update Algorithm
(Change one node)
33. Path Queries II - Complexity
(Per-query analysis)
34. Path Queries II - Implementation
(Pseudocode)
35. Path Queries II - Lessons
(What you learned)
36. Problems - QTREE - Read Statement
(SPOJ classic HLD problem)
37. QTREE - Edge to Vertex Mapping
(Store edge weights at nodes)
38. QTREE - Query Path Edges
(Exclude the LCA)
39. QTREE - Edge Update
Change edge $i$ to weight $ti$
40. QTREE - Complexity
(Same as vertex version)
41. QTREE - Implementation Notes
(Edge indexing)
42. QTREE - Lessons
(Edge queries via HLD)
43. When to Use HLD
(Path queries on trees)
44. HLD vs LCA Binary Lifting
(Updates vs queries)
45. Common Mistakes
(Pitfalls to avoid)
46. Quiz: Heavy Edge Definition
Knowledge check
47. Quiz: Chain Crossing Bound
Knowledge check
48. Quiz: Query Complexity
Knowledge check
49. Section Recap
(What you learned)