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

$ curl repovive.com/roadmaps/data-structures/wavelet-trees

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

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

$ curl repovive.com/roadmaps/data-structures/wavelet-trees

Wavelet Trees

Lessons

1. Intro

2. The Range Counting Problem

3. Binary Representation Insight

Ready to start learning?

4. Wavelet Tree Structure

5. Building the Wavelet Tree

6. Example: Building Step by Step

7. Bitvector Rank Operation

8. Efficient Rank with Prefix Sums

9. Position Mapping

10. Count of Value in Range

11. Range Count by Value Range

12. Problem - Range Frequency Query

13. Range Frequency: Hash Map Approach

14. Range Frequency Solution

15. K-th Smallest in Range

16. K-th Smallest: Why It Works

17. Problem - Kth Smallest in Range

18. Kth Smallest: Merge Sort Tree

19. Wavelet vs Merge Sort Tree

20. Count Less Than in Range

21. Count Greater Than in Range

22. Successor in Range

23. Problem - Count Smaller After Self

24. Count Smaller: Multiple Approaches

25. Count Smaller Solution

26. Space Optimization

27. Coordinate Compression

28. Dynamic Wavelet Trees

29. Wavelet Matrix

30. Wavelet Matrix Operations

31. Application: Mode in Range

32. Application: Range Majority

33. Application: Distinct Count

34. Implementation Tips

35. Common Bugs

36. Quiz: Wavelet Trees

37. Section Recap