A wavelet matrix is a space-optimized variant of wavelet tree.
Instead of a tree with pointers, store bitvectors in a flat array. Each level partitions elements by bit of their value.
class WaveletMatrix:
bitvectors: array of log(sigma) bitvectors
zeros: array of counts (how many 0s at each level)
Navigation uses bit manipulation instead of tree traversal.
Benefits:
- Better cache locality
- Simpler implementation
- Same asymptotic complexity
Wavelet matrices are preferred in practice. Wavelet trees are easier to explain conceptually.