The Range Counting Problem

Given array $A$ of length $n$, answer queries: "count elements in $A[l..r]$ with value in $[a, b]$."

Attempt 1: Segment tree per value Build a segment tree for each distinct value.

Query: sum of counts in $[l, r]$ for values $a$ to $b$.

Problem: $O(\sigma)$ 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: $O(n \log n)$ space and $O(\log^2 n)$ query time.

Wavelet tree solution: $O(n \log \sigma)$ space, $O(\log \sigma)$ queries. Same or better space, faster queries.