Count elements in with value : Two approaches: Approach 1: Use countLess plaintext countGreater(l, r, v) := (r - l + 1) - countLessOrEqual(l, r, v) Approach 2: Direct Similar to countLess but accumulate right subtree counts when is in left half. Count in range : plaintext 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 .
Time: . Space: .