Bitvector Rank Operation

The rank operation counts occurrences of a bit value up to a position:

• $\text{rank}_0(B, i)$ = count of 0s in $B[0..i-1]$
• $\text{rank}_1(B, i)$ = count of 1s in $B[0..i-1]$

function rank(bitvector, bit, i)
    count := 0
    for j from 0 to i - 1
        if bitvector[j] = bit then
            count := count + 1
    return count

Naive: $O(n)$. With preprocessing, you can do $O(1)$ using prefix sums.

Note: $\text{rank}_0(B, i) + \text{rank}_1(B, i) = i$.