Succinct Rank/Select Bitvector

Why Naive Approaches Fail

Consider a bit array of length n and the two operations we care about. First, count how many 1s occur among positions 0 through i, called rank(i). Second, find the position of the k-th 1 bit, called select(k). The naive approach to rank scans from position zero and tallies set bits one at a time, costing time proportional to i in the worst case; the naive approach to select does the same kind of linear walk, costing time proportional to n. For a single query this is fine, but many applications issue millions of these queries against the same fixed bitvector, so linear-time answers become the bottleneck. The obvious fix is to precompute and store the answer to rank at every single index, producing a lookup array the same length as the original bitvector, but with entries large enough to count up to n. That array typically needs many times more space than the original bits themselves, since each stored count requires a full integer's worth of bits while the underlying data was just one bit per position. This defeats the entire motivation for using a compact bitvector, which is often chosen specifically because it packs information into close to the theoretical minimum number of bits. What is needed is a middle ground: an auxiliary structure that is much smaller than the full precomputed-everywhere table, yet still allows every query to be answered without walking through the array from the beginning. This is exactly what makes a structure succinct rather than merely compact: it uses space close to the information-theoretic lower bound for representing the data, plus an extra index whose size is asymptotically negligible in comparison, and still answers queries in constant time. The superblock and block scheme achieves precisely this balance, and it is the classic starting point taught in every succinct data structures course before moving on to more elaborate constructions.

The Two-Level Superblock and Block Index

The classic construction divides the bitvector into large, evenly-sized chunks called superblocks, and each superblock is further divided into smaller chunks called blocks. At the boundary of every superblock, the structure stores one number: the total count of set bits in every position strictly before that superblock, i.e. a running total from the very start of the array. At the boundary of every block, a second, smaller number is stored: the count of set bits within the current superblock only, from that superblock's start up to the current block's start. This two-level split is the key to keeping the index small while still fast. The superblock-level counters need enough bits to represent counts up to n, so there are relatively few of them (roughly n divided by the superblock size), and each one is a fairly wide integer. The block-level counters, in contrast, only ever need to count up to the superblock size, which is chosen to be small, so each block counter can be stored using far fewer bits, even though there are more blocks than superblocks. Choosing superblock size around the square of the block size, or more precisely tying both to logarithmic functions of n, is what makes the total index size shrink to a vanishingly small fraction of the original n bits as n grows. What remains after consulting both stored counters is a short leftover span: the handful of bit positions between the start of the relevant block and the actual query position i. That span is bounded by the block size, which is deliberately kept small, typically on the order of the machine's word size or smaller. Counting the set bits in that short leftover span is the final piece of the puzzle, and it is handled by a fast constant-time popcount step described in the next section, rather than by any further precomputed array walk.

Constant-Time Popcount on the Remainder

After adding the superblock's stored total and the block's stored partial total, what remains is counting the set bits within a short leftover span, no longer than a single block, ending exactly at the queried position i. This final tally must also be constant-time, or the whole scheme would still be linear in the worst case for that last stretch. Two standard techniques accomplish this. The first relies on a hardware popcount instruction, available on virtually all modern processors, which counts the number of set bits in a machine word in a single instruction. If the block size is chosen to fit within one or two machine words, masking off the bits beyond position i and issuing one or two popcount instructions finishes the job instantly, with no memory access beyond the word itself. The second technique, useful when a hardware instruction is unavailable or when working with a software model of the structure, precomputes a small lookup table indexed by every possible bit pattern of a chosen sub-block width, commonly eight or sixteen bits, and stores the popcount of each pattern. Because the number of distinct patterns of width w is only two raised to the power w, this table is minuscule, for example a table for eight-bit patterns has just 256 entries. Looking up the popcount of a short leftover span becomes one or a few table reads plus additions, still constant time and negligible in space. Combining these three pieces, the superblock total, the block's partial total, and the fast popcount of the final short remainder, produces the answer to rank(i) using a fixed, small number of arithmetic operations regardless of how large the overall bitvector is. Select(k) is answered with a similar structure, typically using the same superblock and block boundaries together with either a binary search over the stored counts or a parallel sampling structure that records the position of every m-th set bit directly, letting the search narrow to a small range before a final linear or table-based scan pinpoints the exact position.

Measuring the Space Overhead Precisely

The word succinct has a specific technical meaning: a data structure is succinct when its total space usage is the information-theoretic minimum needed to represent the object, plus a lower-order term that becomes negligible relative to that minimum as the input grows. For an arbitrary bitvector of length n with no special structure, the information-theoretic minimum to store it at all is simply n bits, since there are two raised to the n possible bitvectors of that length and each needs a distinct code. The superblock and block index described here adds roughly order n divided by log n bits on top of those original n bits, using typical parameter choices where block size is proportional to log n and superblock size is proportional to the square of log n. As n grows large, the ratio of index size to data size shrinks toward zero, which is exactly the defining property of a succinct auxiliary structure: it is asymptotically negligible overhead in exchange for constant-time rank and select. This stands in contrast to two other common categories. An implicit structure would use exactly n bits with zero auxiliary overhead, but then rank and select would generally require linear scanning, since there is no room to store any precomputed hints at all. A non-succinct or plain compact structure, on the other hand, might store a full auxiliary array with one entry per bit position, using overhead on the same asymptotic order as the data itself, often several times n bits, which defeats the purpose of choosing a compact representation. The superblock and block scheme occupies the sweet spot between these extremes: close to implicit in space, close to a fully precomputed table in query speed. Real implementations tune the exact superblock and block sizes based on cache line sizes and word width, trading a small constant-factor increase in overhead for better practical performance, while keeping the same asymptotic succinctness guarantee.

The Foundation Underneath Wavelet Trees and Succinct Tries

Rank and select on a plain bitvector might look like a narrow, specialized tool, but it is in fact the load-bearing primitive underneath a large family of more elaborate succinct structures. A wavelet tree, used to represent a sequence over a larger alphabet in compressed form while still supporting rank, select, and access queries on arbitrary symbols, works by recursively splitting the alphabet in half and recording, at every level of a binary tree, which half each symbol fell into as a bitvector. Every query against the wavelet tree as a whole decomposes into a sequence of rank or select queries against these per-level bitvectors, so the wavelet tree's overall query time is entirely dependent on how fast rank and select are on its bitvector components; make each bitvector's rank/select constant-time and the whole tree's queries are logarithmic in the alphabet size, with no linear scanning anywhere. Succinct tree and trie representations tell a similar story. A common technique encodes the shape of a tree using a sequence of balanced parentheses or a similar bit-based encoding, where operations like finding a node's parent, its children, or its subtree size are all expressed as rank and select queries, sometimes together with a related operation for finding matching parenthesis positions. Succinct tries built on top of these tree encodings, used in applications like compressed string dictionaries and indexes for genomic data, inherit their query speed directly from the rank/select performance of the underlying bitvector. Because so many higher-level succinct structures reduce their core operations down to rank and select on a bitvector, optimizing this one foundational structure, choosing good superblock and block sizes, picking an efficient popcount strategy, has an outsized effect across the entire field. This lab's simulator isolates that foundational layer so its behavior can be inspected directly, before it disappears into the recursive machinery of a wavelet tree or a succinct trie.

Frequently asked questions

Try it live

Everything above runs in your browser — open Succinct Rank/Select Bitvector and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.