For this problem, the hash map approach is sufficient and simpler.
However, if you needed to extend to queries like "count values in range " or "find -th smallest in range," the wavelet tree becomes necessary.
Implementation notes:
- Use a dictionary mapping values to sorted lists of indices
- Binary search to count indices in
- Handle missing values gracefully
Time: preprocessing, per query. Space: .