Given array of length , answer queries: "count elements in with value in ."
Attempt 1: Segment tree per value Build a segment tree for each distinct value.
Query: sum of counts in for values to .
Problem: segment trees uses too much memory.
Attempt 2: Merge sort tree Build a segment tree where each node stores the sorted array of values in its range.
Problem: space and query time.
Wavelet tree solution: space, queries. Same or better space, faster queries.