Range Count by Value Range

Count elements in $A[l..r]$ with value in $[a, b]$:

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 $[a, b]$, return the position count immediately.

Time: $O(\log \sigma)$.