Advanced Trees
You know the fundamentals. Now explore HLD, centroid decomposition, treaps, and Euler tour techniques for advanced tree problems.
Lessons
1. Intro
Beyond basic trees
2. Heavy-Light Decomposition
Linearizing tree paths
3. Heavy vs Light Edges
The classification
4. Quiz: Light Edge Bound
Why O(log n)?
5. Building Heavy Chains
DFS construction
6. HLD Construction - Code
The implementation
7. Path Queries with HLD
Using segment trees
8. HLD Path Query - Code
The implementation
9. Problem - Path Queries
HLD in action
10. Path Queries - Analysis
Why HLD?
11. Path Queries - Implementation
Complete solution
12. Lessons from Path Queries
summary
13. Centroid Decomposition
Divide and conquer on trees
14. Finding the Centroid
The algorithm
15. Centroid Finding - Code
The implementation
16. Quiz: Centroid Property
Understanding the guarantee
17. Centroid Decomposition - Structure
The centroid tree
18. Centroid Decomposition - Code
Building the structure
19. Problem - Distance Queries
Classic centroid problem
20. Distance Queries - Analysis
Using centroid ancestors
21. Distance Queries - Implementation
Complete solution
22. Lessons from Distance Queries
summary
23. Treaps - Introduction
Randomized BST
24. Treap Properties
BST + Heap
25. Quiz: Treap Structure
Understanding the shape
26. Treap Operations - Split
Dividing by key
27. Treap Operations - Merge
Combining treaps
28. Treap Insert and Delete
Using split and merge
29. Implicit Treaps
Position-based keys
30. Implicit Treap - Split by Size
Position-based splitting
31. Problem - Cut and Paste
Implicit treap in action
32. Cut and Paste - Analysis
The split-merge dance
33. Cut and Paste - Implementation
Complete solution
34. Lessons from Cut and Paste
summary
35. Euler Tour Technique
Flattening subtrees
36. Euler Tour - Construction
The implementation
37. Subtree Queries with Euler Tour
Range operations
38. HLD vs Euler Tour vs Centroid
Choosing the right tool
39. Problem - Subtree Queries
Euler tour application
40. Subtree Queries - Implementation
Complete solution
41. Challenge: Combined Techniques
Putting it together
42. Section Recap
What you've learned
Practice Problems
Excellent introduction to implicit treap with split/merge and range reverse operations. Teaches implicit key concepts where positions aren't stored explicitly.
Perfect for learning order statistics trees with dynamic updates. Requires counting inversions after swaps using treaps or policy-based data structures.
Dynamic segment trees with coordinate compression for large ranges (n ≤ 10^9). Great for learning split and merge on intervals.
Advanced 2D range query solvable with nested treaps. Teaches transforming permutation problems into geometric queries.
Practice for order statistics trees (policy-based data structures). Requires coordinate compression and range counting.
Dynamic position tracking ideal for order statistics trees. Teaches efficient element movements and position queries in O(log n).
Binary trie for maximum XOR queries. Teaches tree-based approaches to bit manipulation problems as specialized tree structures.
Classic persistent segment trees (Cartesian tree variant). Teaches handling range majority queries efficiently with small k.
Solvable with 26 segment trees or implicit treaps for range sorting. Excellent for understanding lazy propagation and range modifications.
Teaches coordinate compression with balanced trees for DP optimization. Reduces O(n²) solutions to O(n log n) using trees.
Part of SecondThread's dedicated Treap contest. Designed specifically to teach treap concepts with split/merge operations.
Greedy problem benefiting from balanced BST operations. Teaches maintaining dynamic segments with optimal decisions using ordered structures.
Classic order statistics problem solvable with AVL/Red-Black trees. Perfect for learning self-balancing BST implementations.
Requires balanced BST with coordinate compression for range counting. Teaches transforming prefix sum problems into tree-based queries.
Excellent for learning interval trees and TreeMap operations. Requires efficient interval merging and splitting.
Teaches segment trees with coordinate compression and lazy propagation. Great for handling large coordinate spaces efficiently.
Perfect introduction to TreeSet/TreeMap (Red-Black trees). Teaches efficient interval management with O(log n) insertions and merges.
Greedy problem requiring TreeSet for efficient 'next available' queries. Demonstrates practical use of balanced BST higher() operations.
Advanced segment tree with candidate tracking. Teaches building trees for complex queries where nodes maintain aggregate information.
Solvable with dynamic segment trees or balanced TreeMap. Excellent for learning lazy propagation with sparse ranges.