Wavelet Trees
Wavelet trees answer 'count of values in range [l,r] within [a,b]' in O(log max_val).
Lessons
1. Intro
Why wavelet trees matter
2. The Range Counting Problem
Why standard tools fail
3. Binary Representation Insight
The key idea
4. Wavelet Tree Structure
How it's organized
5. Building the Wavelet Tree
Recursive construction
6. Example: Building Step by Step
Concrete walkthrough
7. Bitvector Rank Operation
Count bits up to position
8. Efficient Rank with Prefix Sums
O(1) rank queries
9. Position Mapping
Parent to child indices
10. Count of Value in Range
Frequency query
11. Range Count by Value Range
Count values in [a, b]
12. Problem - Range Frequency Query
Count specific value
13. Range Frequency: Hash Map Approach
Alternative solution
14. Range Frequency Solution
Implement your solution
15. K-th Smallest in Range
Range quantile query
16. K-th Smallest: Why It Works
Binary search on values
17. Problem - Kth Smallest in Range
Online quantile queries
18. Kth Smallest: Merge Sort Tree
Alternative approach
19. Wavelet vs Merge Sort Tree
Trade-offs
20. Count Less Than in Range
Rank query
21. Count Greater Than in Range
Complement query
22. Successor in Range
Next greater value
23. Problem - Count Smaller After Self
Inversion count variant
24. Count Smaller: Multiple Approaches
BIT, segment tree, or wavelet
25. Count Smaller Solution
Implement your solution
26. Space Optimization
Reducing memory usage
27. Coordinate Compression
Shrinking the alphabet
28. Dynamic Wavelet Trees
Supporting updates
29. Wavelet Matrix
More efficient variant
30. Wavelet Matrix Operations
Query implementation
31. Application: Mode in Range
Most frequent element
32. Application: Range Majority
Element appearing > half
33. Application: Distinct Count
Unique values in range
34. Implementation Tips
Practical considerations
35. Common Bugs
Debugging wavelet trees
36. Quiz: Wavelet Trees
Test your understanding
37. Section Recap
What you learned