Wavelet Tree:
- Query:
- Space:
- Best when is small (coordinate compressed)
Merge Sort Tree:
- Query: or
- Space:
- 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.