Introduction

Imagine you have a bitvector — a sequence of nn zeroes and ones. Two questions come up constantly:

  • rank(i): how many 1s appear in positions 1 through ii?
  • select(j): what position holds the jj-th 1?

Answering either question naively means scanning from the start — O(n)O(n) time. That is unacceptable when nn is a billion. The obvious fix is to precompute a table of prefix sums, which answers rank in O(1)O(1), but the table costs another O(nlog⁡n)O(n \log n) bits — many times the original data.

Succinct data structures dissolve that trade-off. The landmark result, proved by Guy Jacobson in 1989, is that you can store the bitvector and all the machinery to answer rank and select in O(1)O(1) time using only n+o(n)n + o(n) bits total — storing the data plus a sub-linear overhead, and nothing more. No pointers, no decompression, no separate index file.

The idea is elegant: organize the precomputed sums at multiple granularities so each level of detail costs only a few bits per block. The blocks fit inside the original data's footprint.

Try It

Below is a 32-bit bitvector. Click any bit to flip it, then pick a query.

<p class="hint">A 32-bit bitvector. Click any bit to flip it. Then choose a <b>rank</b> or <b>select</b> query — the two-level table answers in O(1), with no scanning.</p>
<div id="bits" class="bits-row"></div>
<div class="controls">
  <label>rank(<input id="rank-i" type="number" min="1" max="32" value="16">)
    <button id="btn-rank" type="button">Query rank</button>
  </label>
  <label>select(<input id="sel-j" type="number" min="1" max="32" value="1">)
    <button id="btn-select" type="button">Query select</button>
  </label>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="answer" id="answer"></div>
<div class="table-view" id="table-view"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.bits-row { display: flex; flex-wrap: wrap; gap: 3px; margin-bottom: .6rem; }
.bit { width: 28px; height: 28px; display: flex; align-items: center; justify-content: center;
       font: 700 13px ui-monospace, monospace; border-radius: 5px; cursor: pointer;
       user-select: none; transition: background .12s, color .12s; position: relative; }
.bit.zero { background: #e8eef3; color: #8fa0b0; border: 1px solid #cdd9e3; }
.bit.one  { background: #1d3557; color: #fff; border: 1px solid #162a45; }
.bit.hi   { outline: 3px solid #e63946; outline-offset: 1px; }
.bit .idx { position: absolute; bottom: -14px; font: 400 9px system-ui; color: #aaa; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin: 1.2rem 0 .5rem; }
label { display: flex; align-items: center; gap: .3rem; font-size: .88rem; }
input[type=number] { width: 46px; padding: 3px 5px; border: 1px solid #cdd9e3; border-radius: 5px;
                     font: inherit; text-align: center; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.answer { font: 600 .95rem/1.5 system-ui; min-height: 1.5em; margin: .3rem 0 .6rem; color: #1d3557; }
.answer.err { color: #c92f3c; }
.table-view { font: 400 .8rem/1.6 ui-monospace, monospace; color: #555; background: #f4f7fa;
              border-radius: 6px; padding: .5rem .7rem; max-height: 120px; overflow-y: auto; }
.table-view span.lbl { color: #888; font-size: .75rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Succinct rank/select on a 32-bit bitvector.
// Two-level structure: superblocks of size S, blocks of size B within each superblock.
// sb[i]  = number of 1s in bits[0..i*S-1]  (prefix count at superblock boundaries)
// bl[i]  = number of 1s in bits[sb_start..i*B-1] within the superblock (relative)
// rank(i) = sb[sb_idx] + bl[bl_idx] + popcount(bits[bl_start..i-1])
// select(j) = binary search on sb[], then linear scan within superblock (demo keeps it simple)

const N = 32, S = 8, B = 4; // superblock size 8, block size 4

let bits = new Uint8Array(N); // 0 or 1

// ---- precomputed tables ----
let sb = [], bl = [];

function buildTables() {
  // Superblock prefix counts
  sb = [];
  let cnt = 0;
  for (let i = 0; i < N; i += S) { sb.push(cnt); for (let k = i; k < i + S && k < N; k++) cnt += bits[k]; }
  sb.push(cnt); // sentinel

  // Block prefix counts (relative to superblock start)
  bl = [];
  for (let si = 0; si < N; si += S) {
    let rel = 0;
    for (let bi = si; bi < si + S; bi += B) {
      bl.push(rel);
      for (let k = bi; k < bi + B && k < N; k++) rel += bits[k];
    }
  }
}

function popcount(from, to) { // count 1s in bits[from..to-1]
  let c = 0; for (let i = from; i < to; i++) c += bits[i]; return c;
}

function rank1(i) { // 1-indexed: count 1s in bits[0..i-1]
  if (i <= 0) return 0; if (i > N) i = N;
  const si = Math.floor((i - 1) / S);       // superblock index
  const bi = Math.floor((i - 1) / B);        // block index (global)
  const blRel = bi - Math.floor(si * S / B); // block index relative to superblock
  const blockStart = bi * B;
  return sb[si] + bl[bi - Math.floor(si * S / B) + si * (S / B)] + popcount(blockStart, i);
  // Simpler re-write:
}

// cleaner rank using the tables as built
function rank(i) { // i is 1-based position; counts 1s in positions 1..i
  if (i <= 0) return 0;
  if (i > N) i = N;
  const pos = i - 1; // 0-based
  const sbIdx = Math.floor(pos / S);
  const inSb  = pos - sbIdx * S;
  const blIdx = Math.floor(inSb / B); // block index within superblock
  const blGlobal = sbIdx * (S / B) + blIdx;
  const blStart = sbIdx * S + blIdx * B; // 0-based start of block
  return sb[sbIdx] + bl[blGlobal] + popcount(blStart, pos + 1);
}

function select(j) { // 1-based: find position of the j-th 1 (1-based result)
  if (j <= 0 || j > sb[sb.length - 1]) return -1;
  // binary search on superblock boundaries
  let lo = 0, hi = sb.length - 2;
  while (lo < hi) { const mid = (lo + hi + 1) >> 1; if (sb[mid] < j) lo = mid; else hi = mid - 1; }
  const sbStart = lo * S; // 0-based start of superblock
  // linear scan within superblock
  let rem = j - sb[lo];
  for (let k = sbStart; k < sbStart + S && k < N; k++) {
    rem -= bits[k];
    if (rem === 0) return k + 1; // 1-based
  }
  return -1;
}

// ---- rendering ----
let highlightPos = -1;

function render() {
  buildTables();
  const container = document.getElementById('bits');
  container.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const d = document.createElement('div');
    d.className = 'bit ' + (bits[i] ? 'one' : 'zero') + (i === highlightPos ? ' hi' : '');
    d.textContent = bits[i];
    const idx = document.createElement('span');
    idx.className = 'idx'; idx.textContent = i + 1;
    d.appendChild(idx);
    d.addEventListener('click', () => { bits[i] ^= 1; highlightPos = -1; clearAnswer(); render(); });
    container.appendChild(d);
  }
  renderTable();
}

function renderTable() {
  const tv = document.getElementById('table-view');
  const total = sb[sb.length - 1];
  tv.innerHTML =
    fmt('<span class="lbl">Superblock prefix counts (every 8 bits):</span> %map%<br><span class="lbl">Block counts within superblocks (every 4 bits):</span> %map2%<br><span class="lbl">Total 1s in bitvector:</span> %total%', { map: sb.slice(0, -1).map((v, i) => 'sb[' + i + ']=' + v).join('  '), map2: bl.map((v, i) => 'bl[' + i + ']=' + v).join('  '), total: total });
}

function clearAnswer() { const a = document.getElementById('answer'); a.textContent = ''; a.className = 'answer'; }

function setAnswer(text, err) {
  const a = document.getElementById('answer'); a.textContent = text; a.className = 'answer' + (err ? ' err' : '');
}

document.getElementById('btn-rank').addEventListener('click', () => {
  const i = parseInt(document.getElementById('rank-i').value, 10);
  if (isNaN(i) || i < 1 || i > N) { setAnswer(fmt('i must be 1– %N%', { N: N }), true); return; }
  const r = rank(i);
  highlightPos = i - 1;
  render();
  setAnswer(fmt('rank(%i%) = %r%  — there are %r% one(s) in positions 1.. %i%.', { i: i, r: r }), false);
});

document.getElementById('btn-select').addEventListener('click', () => {
  const j = parseInt(document.getElementById('sel-j').value, 10);
  if (isNaN(j) || j < 1) { setAnswer('j must be ≥ 1', true); return; }
  const pos = select(j);
  if (pos === -1) {
    highlightPos = -1; render();
    setAnswer(fmt('select(%j%) = undefined — there are fewer than %j% ones.', { j: j }), true);
  } else {
    highlightPos = pos - 1; render();
    setAnswer(fmt('select(%j%) = %pos%  — the %j% -th one is at position %pos%.', { j: j, pos: pos }), false);
  }
});

document.getElementById('btn-reset').addEventListener('click', () => {
  bits.fill(0); highlightPos = -1; clearAnswer(); render();
});

// default pattern: alternating
for (let i = 0; i < N; i++) bits[i] = i % 3 === 0 ? 1 : 0;
render();
Result
Console

The demo precomputes a two-level table (superblocks and blocks) after every edit — the same structure used in real implementations. Rank answers in two table look-ups plus a popcount of a few bits. Select inverts rank with a binary search over superblock boundaries, then refines inside one block. No position is ever scanned from scratch.

The Real Complexity

How much space do you really need to support rank and select in O(1)O(1)?

  • Lower bound: any data structure that answers rank in O(1)O(1) must store at least nn bits just to encode the bitvector itself. Any constant-time rank structure therefore uses Ω(n)\Omega(n) bits.
  • Upper bound — Jacobson's construction (1989): divide the bitvector into superblocks of s=(log⁡n)2/2s = (\log n)^2 / 2 bits, storing the prefix 1-count at each superblock boundary in O(n/s⋅log⁡n)=o(n)O(n / s \cdot \log n) = o(n) bits. Subdivide each superblock into blocks of b=(log⁡n)/2b = (\log n) / 2 bits, storing the within-superblock prefix count at each block boundary in another o(n)o(n) bits. For the remaining bits inside each block, precompute a universal lookup table of size O(nlog⁡n)=o(n)O(\sqrt{n} \log n) = o(n) bits that gives the popcount of any bb-bit string up to any offset. Querying rank(i) then costs two table look-ups plus one popcount — O(1) worst-case time, n+o(n)n + o(n) bits total.
  • Select is achieved (proven O(1) by Munro in 1996 and refined by Clark in 1996) by binary search on superblock boundaries (O(log⁡log⁡n)O(\log \log n) steps) plus a block-level table — also o(n)o(n) extra bits.
  • The result is essentially tight: information-theoretically the bitvector itself demands nn bits, and o(n)o(n) overhead cannot be avoided if you need O(1)O(1) queries, because storing nothing extra forces you to scan.

This is a proved result — not a conjecture, not an open problem. Jacobson's 1989 paper settled it, and every compressed text index, wavelet tree, and FM-index built since then rests on this foundation.

Compare with the naive trade-off: an unadorned bitvector gives O(n)O(n) query time, and a full precomputed table gives O(1)O(1) time but O(nlog⁡n)O(n \log n) bits. Jacobson showed the middle ground is real: O(1)O(1) time and n+o(n)n + o(n) bits.

For deeper context on why constant-time data structures matter, see P vs NP — succinct rank/select is one of the clearest examples of a provably optimal algorithm.

Where It Matters

"Answer this query in O(1) without ballooning the memory" is one of the most valuable guarantees in systems that handle enormous data:

  • Compressed text indexes: the FM-index (Ferragina & Manzini, 2000) compresses a text and allows substring search, using rank/select as its inner loop. Searching gigabytes of DNA for a short pattern costs O(m)O(m) steps, where mm is the pattern length, regardless of the database size.
  • Wavelet trees: a data structure that answers range queries and supports order statistics on compressed sequences — built from layers of bitvectors, each queried via rank/select.
  • Genome assembly: tools like BWA and Bowtie index the human genome (~3 billion bases) in a few gigabytes using FM-index techniques, making personalized medicine economically feasible.
  • Inverted indexes in search engines: document frequency look-ups and posting-list navigation use succinct structures to fit massive indexes in RAM.
  • XML and JSON navigation: tree ordinal operations (child, parent, sibling) on compressed document trees reduce to rank/select on a parenthesis sequence.

Learn this one trick and you understand the spine of pattern matching at genomic scale, and why data that once required a server room now fits on a laptop.

Conclusion

Succinct rank/select is one of the cleanest wins in all of data structures: a problem with an obvious lower bound (nn bits), an obvious upper bound (O(nlog⁡n)O(n \log n) bits for O(1)O(1) queries), and a proved construction that achieves both in the same breath — n+o(n)n + o(n) bits and O(1)O(1) time.

The trick — organize precomputed sums at two levels of granularity so each level costs only a vanishing fraction of nn — has been copied into virtually every compressed index built in the last thirty years. The next time a genome browser responds in milliseconds, or a search engine serves results from terabytes of text, rank/select is doing the quiet work inside.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/succinct-rank-select/Content licensed under CC BY-NC 4.0.