Section Recap

Wavelet trees answer range queries on sequences. Structure: Binary tree where each node splits alphabet.

Left child gets smaller half, right gets larger half. Core Operations:

• Rank: Count occurrences of symbol in prefix
• Select: Find k-th occurrence of symbol
• Range quantile: k-th smallest in range

core idea: Recursively halve alphabet, use bitvectors at each level.

Complexity: $O(\log \sigma)$ per query where $\sigma$ is alphabet size. Space: $O(n \log \sigma)$.