You have a sequence of values.
You need to answer queries like: - "How many values in positions are between and ?" - "What is the -th smallest value in range ?" - "How many times does value appear in range ?" Brute force scans the range: per query.
With many queries, that's too slow. Wavelet trees answer these in where is the number of distinct values.
For typical problems, , 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.