Wavelet Tree Range Quantiles

The Wavelet Tree is a succinct data structure that stores strings or arrays in compressed space while answering queries such as range quantiles, rank, and select in O(log σ) time, where σ is the alphabet size. It navigates stable value partitions to answer subarray quantile and rank queries without physically sorting the subarray at query time.

Interactive Experiment

To see how the wavelet tree structure efficiently answers queries, you can interact with the Wavelet Tree Range Quantiles module by following these steps:

1. Set the Array select to "Mixed" to load the default dataset.
2. Set the Left index to 0 and the Right index to 7 to select the entire array.
3. Set the Rank to 4 to search for the 4th smallest value in the selected range.
4. Observe the highlighted traversal path in the canvas. The tree navigates the partitions, updating the index ranges at each depth.
5. Change the Value probe to 5 to observe how the tree also efficiently calculates the count of elements less than or equal to the probe in the specified range.