Count Less Than in Range

Count elements in $A[l..r]$ with value $< v$:

function countLess(node, l, r, v)
    if l > r or v <= node.lo then
        return 0
    if node.hi < v then
        return r - l + 1

    mid := (node.lo + node.hi) / 2

    leftL := rank0(node.bitvector, l)
    leftR := rank0(node.bitvector, r + 1) - 1
    rightL := rank1(node.bitvector, l)
    rightR := rank1(node.bitvector, r + 1) - 1

    if v <= mid + 1 then
        return countLess(node.left, leftL, leftR, v)
    else
        leftCount := leftR - leftL + 1
        rightCount := countLess(node.right, rightL, rightR, v)
        return leftCount + rightCount

If $v$ is in the right half, all left subtree elements are less than $v$.

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