Count elements in with value in :
function rangeCount(node, l, r, a, b)
if l > r or b < node.lo or a > node.hi then
return 0
if a <= node.lo and node.hi <= b then
return r - l + 1
mid := (node.lo + node.hi) / 2
// Map positions to children
leftL := rank0(node.bitvector, l)
leftR := rank0(node.bitvector, r + 1) - 1
rightL := rank1(node.bitvector, l)
rightR := rank1(node.bitvector, r + 1) - 1
leftCount := rangeCount(node.left, leftL, leftR, a, b)
rightCount := rangeCount(node.right, rightL, rightR, a, b)
return leftCount + rightCount
When a node's value range is fully inside , return the position count immediately.
Time: .