#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/bitvector-rank-operation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/bitvector-rank-operation

Repovive

Bitvector Rank Operation - Wavelet Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Bitvector Rank Operation

Count bits up to position

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$ .