Wavelet vs Merge Sort Tree

Wavelet Tree:

• Query: $O(\log \sigma)$
• Space: $O(n \log \sigma)$
• Best when $\sigma$ is small (coordinate compressed)

Merge Sort Tree:

• Query: $O(\log^2 n)$ or $O(\log^3 n)$
• Space: $O(n \log n)$
• Simpler to implement

When to use which:

• Wavelet tree: many queries, small alphabet, need other queries (range count by value)
• Merge sort tree: simpler implementation, one-off usage

In competitive programming, wavelet tree is preferred for its versatility. In interviews, merge sort tree is more commonly asked.