Dynamic Wavelet Trees

Standard wavelet trees are static: no insertions, deletions, or value changes.

For dynamic operations, replace bitvectors with balanced BSTs or other dynamic rank structures.

class DynamicWaveletNode:
    lo, hi: int
    tree: balanced BST storing (position, bit) pairs
    left: DynamicWaveletNode
    right: DynamicWaveletNode

Operations:

• Insert: add to BSTs along the path
• Delete: remove from BSTs along the path
• Query: same logic, use BST rank

Time: $O(\log n \cdot \log \sigma)$ per operation.

Dynamic wavelet trees are complex. For most problems, rebuild the static tree when needed.