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: 2D segment tree Build a 2D structure on (position, value).
Problem: space and queries. Wavelet tree solution: space, queries. Better space than 2D, same or better query time.