A wavelet tree is a binary tree where:
- Root handles all values in alphabet
- Each node handles a value range and stores a bitvector
- Left child handles lower half of values
- Right child handles upper half
At each node, the bitvector marks which elements go right (1) or left (0) based on whether their value is in the upper or lower half of the node's range.
class WaveletNode:
lo, hi: int // value range this node handles
bitvector: array of bits
left: WaveletNode // values in [lo, mid]
right: WaveletNode // values in [mid+1, hi]
The bitvector is the key: it lets us map positions from parent to children.