Count Greater Than in Range

Count elements in $A[l..r]$ with value $> v$: Two approaches:

Approach 1: Use countLess pseudocode countGreater(l, r, v) := (r - l + 1) - countLessOrEqual(l, r, v)

Approach 2: Direct Similar to countLess but accumulate right subtree counts when $v$ is in left half.

Count in range $[a, b]$: pseudocode countInRange(l, r, a, b) := countLessOrEqual(l, r, b) - countLess(l, r, a) All these queries reduce to counting with value bounds, which wavelet trees handle in $O(\log \sigma)$.

Time: $O(\log \sigma)$ per query. Space: $O(n \log \sigma)$.