Intro

You have a sequence of values.

You need to answer queries like:

• "How many values in positions $[l, r]$ are between $a$ and $b$?"
• "What is the $k$-th smallest value in range $[l, r]$?"
• "How many times does value $v$ appear in range $[l, r]$?"

Brute force scans the range: $O(n)$ per query.

With many queries, that's too slow. Wavelet trees answer these in $O(\log \sigma)$ where $\sigma$ is the number of distinct values.

For typical problems, $\sigma \leq 10^6$, so queries take about $20$ operations. In this section, I'll show you how wavelet trees work, how to build them, and how to use them for range frequency, range quantile, and range counting queries.