Rank Query: Counting Set Bits in Bitvectors

The rank query is a fundamental operation in succinct data structures that counts the number of set bits (ones) up to a specified index in a bitvector. While a naive scan through the binary sequence solves this linearly, modern computer science uses a combination of hardware-level bitwise operations and multi-level precomputed index structures to achieve constant time \(O(1)\) evaluation with minimal memory overhead.

The Fundamental Concept of Rank

A bitvector (or bitmap) is a compact array of binary digits (\(0\) and \(1\)). Given an index \(i\), the query \(\text{rank}_1(i)\) returns the number of \(1\)s occurring in the prefix \(B[0 \dots i]\). Similarly, \(\text{rank}_0(i)\) counts the number of \(0\)s, which can be derived directly using the identity:

\[\text{rank}_0(i) = (i + 1) - \text{rank}_1(i)\]

Baseline: Word-Level Popcount

At the machine level, bitvectors are stored as arrays of fixed-width machine words (typically 64-bit integers).

To count the bits up to index \(i\) without precomputed structures: 1. Identify the word index containing bit \(i\): \(\lfloor i / 64 \rfloor\). 2. Sum the set bits of all preceding words using CPU-level population count instructions (such as POPCNT on x86/x64 architectures). 3. Mask the target word to isolate bits up to position \((i \bmod 64)\) and apply POPCNT to the masked segment.

While this approach is space-efficient (requiring zero auxiliary storage), its query time is \(O(i/64)\), which degrades linearly as the bitvector grows.

Constant-Time Rank via Two-Level Indexing

To achieve true \(O(1)\) time complexity, bitvectors use a two-level indexing scheme (popularized by Guy Jacobson) that divides the bit array into hierarchical blocks:

  1. Superblocks: The bitvector of length \(n\) is divided into large superblocks of size \(S = \lfloor \log^2 n \rfloor\) bits. An array stores the absolute number of \(1\)s from the start of the bitvector up to the beginning of each superblock.
  2. Blocks (Sub-blocks): Each superblock is further subdivided into smaller blocks of size \(b = \lfloor \frac{1}{2} \log n \rfloor\) bits. A secondary array stores the relative number of \(1\)s from the start of the containing superblock up to the beginning of each block.

Because relative counts within a superblock are bounded by \(S\), they require significantly fewer bits to store than global counts.

Executing the Rank Query

When computing \(\text{rank}_1(i)\), the query executes three operations:

  1. Superblock Lookup: Retrieve the absolute count of set bits before the target superblock index \(\lfloor i / S \rfloor\).
  2. Block Lookup: Retrieve the relative count of set bits from the start of the superblock up to the target sub-block index \(\lfloor i / b \rfloor\).
  3. In-Block Resolution: Count the remaining set bits within the target sub-block up to \((i \bmod b)\) using either a CPU POPCNT instruction or a precomputed lookup table.

The final rank is the sum of these three values:

\[\text{rank}_1(i) = \text{SuperblockCount} + \text{BlockCount} + \text{InBlockPopcount}\]

Complexity and Efficiency