Wavelet Tree Range Quantiles

Concept Overview

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.

Worked Example

Consider the array [3, 1, 4, 1, 5, 9, 2, 6] with values from 1 to 9. We want to find the 4th smallest element (rank 4) in the subarray from index 0 to 7. The alphabet range is [1, 9], so the root node splits on mid = floor((1+9)/2) = 5.

Array: [3, 1, 4, 1, 5, 9, 2, 6]
Min: 1, Max: 9, Mid: 5

Step 1: Root Node [1, 9]
Values <= 5 (0): 3, 1, 4, 1, 5, 2
Values > 5  (1): 9, 6
Bit Vector: 0 0 0 0 0 1 0 1
Zeros in range [0, 7]: 6
Since k=4 <= 6, we go LEFT.

Step 2: Left Child [1, 5]
Mapped Range: [0, 5], New k: 4
Values: [3, 1, 4, 1, 5, 2]
Mid: floor((1+5)/2) = 3
Bit Vector: 0 0 1 0 1 0
Zeros in [0, 5]: 4
Since k=4 <= 4, we go LEFT.

Step 3: Left-Left Child [1, 3]
Mapped Range: [0, 3], New k: 4
Values: [3, 1, 1, 2]
Mid: floor((1+3)/2) = 2
Bit Vector: 1 0 0 0
Zeros in [0, 3]: 3
Since k=4 > 3, we go RIGHT.
New k = 4 - 3 = 1

Step 4: Right Child [3, 3]
Mapped Range: [0, 0] (only 1 element mapped to 1s)
Leaf node reached. Value is 3.

Result: The 4th smallest element is 3.

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:

Set the Array select to "Mixed" to load the default dataset.
Set the Left index to 0 and the Right index to 7 to select the entire array.
Set the Rank to 4 to search for the 4th smallest value in the selected range.
Observe the highlighted traversal path in the canvas. The tree navigates the partitions, updating the index ranges at each depth.
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.

Limitations and Boundaries

The Wavelet Tree is highly efficient, but its depth depends on the alphabet size σ, requiring O(log σ) traversal steps per query. For an empty array, quantile and rank queries are undefined, returning "Unavailable", and the root partition becomes "Empty". The UI handles indices dynamically; selecting a left index greater than the right index automatically sorts them to form a valid clamped range.

References

This section outlines the primary research and literature that formalizes the operations used in Wavelet Trees.

Wavelet Trees for All (Navarro) — Discusses the fundamentals of wavelet trees, range queries, and practical implementations.

Wavelet Tree Range Quantiles