Space Optimization

Standard wavelet tree uses $O(n \log \sigma)$ space for bitvectors.

Can we do better?

Technique 1: Implicit structure Store all bitvectors in one array of size $n \cdot \lceil \log \sigma \rceil$ bits. Move through by computing offsets.

Technique 2: Succinct bitvectors Use rank/select structures that store bitvectors in compressed form with $O(1)$ rank queries.

Technique 3: Pointerless wavelet tree Store the tree implicitly like a heap.

Node $i$ has children $2i$ and $2i+1$. No pointer overhead. For competitive programming, the standard implementation is usually fine. Space optimization matters for production systems with billions of elements.