Succinct Rank/Select

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

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

Answering either question naively means scanning from the start — $O(n)$ time. That is unacceptable when $n$ is a billion. The obvious fix is to precompute a table of prefix sums, which answers rank in $O(1)$, but the table costs another $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)$ time using only $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.

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

<p class="hint">{{hint}}</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">{{btn_rank}}</button>
  </label>
  <label>select(<input id="sel-j" type="number" min="1" max="32" value="1">)
    <button id="btn-select" type="button">{{btn_select}}</button>
  </label>
  <button id="btn-reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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

• Lower bound: any data structure that answers rank in $O(1)$ must store at least $n$ bits just to encode the bitvector itself. Any constant-time rank structure therefore uses $\Omega(n)$ bits.
• Upper bound — Jacobson's construction (1989): divide the bitvector into superblocks of $s = (\log n)^2 / 2$ bits, storing the prefix 1-count at each superblock boundary in $O(n / s \cdot \log n) = o(n)$ bits. Subdivide each superblock into blocks of $b = (\log n) / 2$ bits, storing the within-superblock prefix count at each block boundary in another $o(n)$ bits. For the remaining bits inside each block, precompute a universal lookup table of size $O(\sqrt{n} \log n) = o(n)$ bits that gives the popcount of any $b$-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)$ 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)$ steps) plus a block-level table — also $o(n)$ extra bits.
• The result is essentially tight: information-theoretically the bitvector itself demands $n$ bits, and $o(n)$ overhead cannot be avoided if you need $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)$ query time, and a full precomputed table gives $O(1)$ time but $O(n \log n)$ bits. Jacobson showed the middle ground is real: $O(1)$ time and $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.

"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)$ steps, where $m$ 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.

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

The trick — organize precomputed sums at two levels of granularity so each level costs only a vanishing fraction of $n$ — 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.