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: .