↩ back to Array-Backed Trees

Bit Vector Rank/Select

Wavelet Tree's own Pitfalls section names the piece its reference implementation skips: a per-level prefix0 array that costs O(n) extra ints just to make rank-on-a-bit-array O(1), "in its succinct real-world form, not built here." This page is that real-world form: given a fixed array of bits, answer rank1(i) (how many 1-bits sit in positions [0, i)) and select1(k) (where the k-th 1-bit sits, 1-indexed) without ever scanning the range in question — using a structure whose own overhead is o(n) bits, asymptotically smaller than the n raw bits it indexes, not just a constant multiple of them.

Try it

The 32 bits below are chopped into blocks of 4 (thin dashed edge) and superblocks of two blocks each, 8 bits (thick edge). Pick an operation and a value, press Query, then step through to see exactly which precomputed table entries answer it — no cell to the left of the target is ever re-scanned.

Why it works

A block's own bit pattern is all a within-block query ever needs. A block of size b has only 2^b possible patterns — the same observation ±1 RMQ's per-shape lookup table relies on, applied here to a plain 0/1 pattern instead of an up/down shape. Precompute, once per pattern, a popcount-prefix array (how many 1-bits sit in the pattern's first k bits, for every k) and a select array (which offset holds the pattern's r-th 1-bit, for every r) — every block that happens to share a pattern reuses the identical table entry, block 0 and block 2 in the demo above both being 1101.

Two levels of prefix sums turn "which block" into array indexing instead of accumulation. Adding up every earlier block's popcount one at a time on every query would cost O(n/b) — better than scanning raw bits, but still not O(1). Splitting the running total into two arrays fixes that without inflating either one: superRank[s] holds the absolute count of 1-bits before superblock s, and blockRankInSuper[block] holds the count relative to its own superblock's start — so rank1(i) is exactly one lookup in each array plus one pattern-table lookup, added together, never a loop over any earlier block or bit:

Block 5 sits second in superblock 2 (blocks 4 and 5), so its rank-in-superblock is block 4's popcount (1) — not its own. rank1(19) on the demo: block ⌊19/4⌋ = 4, offset 19 − 16 = 3, superblock ⌊4/2⌋ = 2. superRank[2] = 9 (blocks 0-3's total), plus blockRankInSuper[4] = 0 (block 4 is first in its superblock), plus the pattern-table lookup for 0001's first 3 bits (000, popcount 0), giving 9 + 0 + 0 = 9.

select1 runs the same idea in reverse, but has to search for the answer instead of computing it directly. superRank is non-decreasing, so a binary search over it finds the superblock containing the k-th 1-bit in O(log(n/S)) steps, where S is the superblock size; a short scan over that superblock's few blocks (using blockRankInSuper the same way) finds the exact block; one select-table lookup, keyed on the block's own pattern, gives the exact offset. Both pieces depend on how many superblocks and blocks-per-superblock exist, not on n directly — see Complexity below for why that still works out to O(log n) overall, asymptotically worse than rank1's O(1).

Reference implementation

Build precomputes one pattern table (shared by every block with that pattern), then the two levels of prefix sums:

function buildRankSelect(bits, blockSize, blocksPerSuper) {
  const n = bits.length;
  const numBlocks = Math.ceil(n / blockSize);
  const numSuper = Math.ceil(numBlocks / blocksPerSuper);
  const numPatterns = 1 << blockSize;

  // one popcount-prefix array and one position-of-kth-1 array per distinct block pattern
  const PREFIX = [], SELECT = [];
  for (let p = 0; p < numPatterns; p++) {
    const prefix = [0], positions = [];
    for (let j = 0; j < blockSize; j++) {
      const bit = (p >> (blockSize - 1 - j)) & 1;
      prefix.push(prefix[j] + bit);
      if (bit) positions.push(j);
    }
    PREFIX.push(prefix);
    SELECT.push(positions);
  }

  const blockPattern = [], blockPopcount = [];
  for (let b = 0; b < numBlocks; b++) {
    const start = b * blockSize, end = Math.min(start + blockSize, n);
    let pattern = 0;
    for (let i = start; i < end; i++) pattern = (pattern << 1) | bits[i];
    pattern <<= (blockSize - (end - start));   // zero-pad a short final block on the right
    blockPattern.push(pattern);
    blockPopcount.push(PREFIX[pattern][end - start]);
  }

  // two-level prefix sums: blockRankInSuper is relative to its own superblock's start,
  // superRank is absolute — the split that keeps both arrays' entries small (see Complexity)
  const blockRankInSuper = new Array(numBlocks);
  const superRank = new Array(numSuper + 1).fill(0);
  for (let s = 0; s < numSuper; s++) {
    let acc = 0;
    const startB = s * blocksPerSuper, endB = Math.min(startB + blocksPerSuper, numBlocks);
    for (let b = startB; b < endB; b++) { blockRankInSuper[b] = acc; acc += blockPopcount[b]; }
    superRank[s + 1] = superRank[s] + acc;
  }
  const total = superRank[numSuper];

  function rank1(i) {                          // # of 1-bits in bits[0, i)
    if (i <= 0) return 0;
    if (i >= n) return total;
    const block = Math.floor(i / blockSize);
    const offset = i - block * blockSize;
    const sb = Math.floor(block / blocksPerSuper);
    return superRank[sb] + blockRankInSuper[block] + PREFIX[blockPattern[block]][offset];
  }

  function select1(k) {                        // position of the k-th 1-bit, 1-indexed
    if (k < 1 || k > total) return -1;
    let lo = 0, hi = numSuper - 1;              // smallest sb with superRank[sb+1] >= k
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (superRank[mid + 1] >= k) hi = mid; else lo = mid + 1;
    }
    const sb = lo;
    const kInSuper = k - superRank[sb];
    const startB = sb * blocksPerSuper, endB = Math.min(startB + blocksPerSuper, numBlocks);
    let block = startB;
    for (let b = startB; b < endB; b++) {
      block = b;
      if (blockRankInSuper[b] + blockPopcount[b] >= kInSuper) break;
    }
    const within = kInSuper - blockRankInSuper[block] - 1;
    return block * blockSize + SELECT[blockPattern[block]][within];
  }

  return { rank1, select1, total };
}

const bits = [1,1,0,1, 0,0,1,0, 1,1,0,1, 0,0,1,1, 0,0,0,1, 1,0,1,1, 0,1,0,0, 1,0,1,1];
const rs = buildRankSelect(bits, 4, 2);
rs.rank1(19);       // 9  — nine 1-bits sit at positions 0..18
rs.select1(10);      // 19 — position 19 holds the 10th 1-bit

Pitfalls

Skipping the within-superblock term. superRank alone gives the right count for a block that happens to sit first in its superblock — it's tempting to stop there and answer every block with superRank[sb] + PREFIX[...], treating blockRankInSuper as redundant bookkeeping. Measured directly: building 3,000 random bit vectors (lengths 1-500, block/superblock sizes randomized so more than one block per superblock is common) and comparing rank1 against an independent scan across 60,000 randomized query points, that shortcut is wrong 62.5% of the time (37,525 of 60,000) — because most blocks in a multi-block superblock aren't the first one, and skip exactly the popcount of every block before them within their own superblock.

An off-by-one in select1's binary search silently searches for the wrong superblock. The search above narrows on superRank[mid+1] >= k; writing that one comparison as strict > instead looks harmless — it still narrows the range on every step and always terminates — but lands one superblock later than the correct one whenever k exactly equals a superblock boundary's cumulative count, a real and common case, not an edge case that only shows up at the array's ends. Measured directly: same 3,000 random bit vectors, every valid k from 1 to that vector's total 1-count (376,029 trials total), wrong 22.1% of the time.

Complexity

Time: rank1 is O(1) — one lookup in each of superRank, blockRankInSuper, and the winning block's own pattern-prefix row, never a loop whose length depends on i. select1 is O(log n) — a binary search over numSuper = n/S superblocks (O(log(n/S))) followed by a scan over that superblock's own blocksPerSuper = S/b blocks (O(S/b)), where S is the superblock size and b the block size; with the space-driven choices below both terms work out to O(log n) — a real, known asymmetry between the two operations, not a gap in this particular reference implementation. A fully O(1) select needs one more structure on top (sampling every r-th 1-bit's own position, so a binary search is never needed at all) — a genuine further extension, not built here.

Space: the whole point is staying o(n) bits of extra space beyond the n raw bits, which only holds for the right choice of block size b and superblock size S, not any fixed constant. The pattern tables cost O(2^b · b) bits total regardless of n — the same b ≈ (log₂n)/2 choice ±1 RMQ's own shape table relies on keeps that O(√n · log n), itself o(n). blockRankInSuper needs only O(log S) bits per entry (it never exceeds one superblock's own count) across n/b blocks; superRank needs the full O(log n) bits per entry but only across n/S superblocks. Picking S ≈ (log₂n)² makes both of those o(n) too — a reference implementation in plain JS (this page's demo included) stores every one of these as a full-width number regardless, same as ±1 RMQ's own reference code; the o(n) bound is a real, achievable property of the scheme, not a claim about this exact JavaScript array's byte size.