#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition

Lessons

1. Intro

2. The Path Query Problem

3. Why Subtree Tricks Fail

Practice Problems

Ready to start learning?

4. The Chain Idea

5. Subtree Size

6. Heavy and Light Edges

7. Heavy Paths as Chains

8. The $O(\log n)$ Chain Property

9. Path to LCA Structure

10. Chain Decomposition DFS

11. Chain Positions

12. Chain Heads

13. Segment Tree per Chain

14. Single Segment Tree Improvement

15. Path Query Algorithm

16. Depth Array

17. Parent Array

18. Update Operation

19. Edge Queries vs Vertex Queries

20. LCA in HLD

21. Complexity Analysis

22. Implementation - Preprocessing

23. Implementation - Decomposition

24. Implementation - Segment Tree

25. Implementation - Path Query

26. Path Updates

27. Path Sum Queries

28. Problems - Path Queries II - Read Statement

29. Path Queries II - Heavy Edges

30. Path Queries II - Segment Tree

31. Path Queries II - Query Algorithm

32. Path Queries II - Update Algorithm

33. Path Queries II - Complexity

34. Path Queries II - Implementation

35. Path Queries II - Lessons

36. Problems - QTREE - Read Statement

37. QTREE - Edge to Vertex Mapping

38. QTREE - Query Path Edges

39. QTREE - Edge Update

40. QTREE - Complexity

41. QTREE - Implementation Notes

42. QTREE - Lessons

43. When to Use HLD

44. HLD vs LCA Binary Lifting

45. Common Mistakes

46. Quiz: Heavy Edge Definition

47. Quiz: Chain Crossing Bound

48. Quiz: Query Complexity

49. Section 16 Recap