Small-to-Large Merging
You know how to process subtrees. Now merge results from children using small-to-large merging.
Lessons
1. Intro
(The merging problem)
2. The Merging Problem
(Combining child results)
3. Naive Merging
(Why it fails)
4. Worst Case: Chain Tree
(O(n²) disaster)
5. The Core idea
(Merge small into large)
6. Why O(n log n) Works
(Doubling argument)
7. Implementation Pattern
(DSU on tree structure)
8. Code Structure
(High-level template)
9. Tracking Subtree Sizes
(First DFS pass)
10. Reusing the Largest Set
(Memory optimization)
11. Problem - Distinct Colors
(CSES 1139)
12. Distinct Colors - Naive Approach
(Why it times out)
13. Distinct Colors - Algorithm
(Small-to-large merging)
14. Distinct Colors - Implementation
(C++ with sets)
15. Distinct Colors - Walkthrough
(Example execution)
16. Distinct Colors - Lessons
(What you learned)
17. Problem - Lomsat gelral
(Codeforces 600E)
18. Lomsat gelral - Observation
(Frequency tracking)
19. Lomsat gelral - Algorithm
(Small-to-large on maps)
20. Lomsat gelral - Maintaining the Max
(Tracking maximum frequency)
21. Lomsat gelral - Implementation
(C++ with maps)
22. Lomsat gelral - Walkthrough
(Example execution)
23. Lomsat gelral - Lessons
(What you learned)
24. When to Use Small-to-Large
(Pattern recognition)
25. Alternatives to Small-to-Large
(Other techniques)
26. Memory Considerations
(Space complexity)
27. Connection to Heavy-Light Decomposition
(Heavy child concept)
28. Implementation Tips
(Avoiding bugs)
29. Debugging Small-to-Large
(Common mistakes)
30. Quiz: Small-to-Large Complexity
Knowledge check
31. Quiz: Small-to-Large Use
Knowledge check
32. Variations of the Technique
(Beyond basic merging)
33. Practice Tips
(Building intuition)
34. Common Problem Variations
(What to expect)
35. Online vs Offline
(Query handling)
36. Space Improvement
(Reducing memory usage)
37. Constant Factors
(Practical performance)
38. Combining with Other Techniques
(Advanced applications)
39. Historical Note
(DSU on tree origin)
40. Section Recap
(What you learned)