Coordinate Compression

When values range up to $10^9$ but there are only $n$ distinct values, compress:

function compress(arr)
    sorted := sort(unique(arr))
    mapping := map from value to compressed index
    for i from 0 to length(sorted) - 1
        mapping[sorted[i]] := i

    for i from 0 to length(arr) - 1
        arr[i] := mapping[arr[i]]

Now alphabet size $\sigma = n$ instead of $10^9$.

This reduces wavelet tree depth from $30$ to $\log n \approx 17$.

Always compress when values are sparse. The queries work the same; just remember to translate results back if needed.