Wavelet Matrix

A wavelet matrix is a space-optimized variant of wavelet tree.

Instead of a tree with pointers, store $\log \sigma$ bitvectors in a flat array. Each level $i$ partitions elements by bit $i$ 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.