Binary Representation Insight

Think of each value in binary. To find values in a range, you can filter by bit positions.

For alphabet $[0, 7]$ ($3$ bits):

• Values with highest bit 0: $\{0, 1, 2, 3\}$
• Values with highest bit 1: $\{4, 5, 6, 7\}$

If you're looking for values in $[2, 5]$, you need some from each group.

The wavelet tree recursively partitions values by their bits. At each level, you split: values with bit 0 go left, values with bit 1 go right. You get a binary tree of depth $\log \sigma$ where each node handles a range of values.