Count of Value in Range

Count occurrences of value $v$ in $A[l..r]$:

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

    mid := (node.lo + node.hi) / 2
    if v <= mid then
        // v is in left subtree
        newL := rank0(node.bitvector, l)
        newR := rank0(node.bitvector, r + 1) - 1
        return count(node.left, newL, newR, v)
    else
        // v is in right subtree
        newL := rank1(node.bitvector, l)
        newR := rank1(node.bitvector, r + 1) - 1
        return count(node.right, newL, newR, v)

Follow the path to value $v$, narrowing the range at each step.

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