Succinct Bitvectors & Wavelet Trees

1. Introduction & Motivation

Succinct is a precise technical claim, not a synonym for "compressed." A succinct data structure stores its data using space close to the information-theoretic minimum number of bits required to represent it, while still supporting the same queries a plain, uncompressed representation would support — and it answers those queries directly on the compact representation, in time close to what the uncompressed structure would need.

Contrast that with ordinary compression. A gzip-compressed array is small, but to ask "what is the value at index 1000?" you typically must decompress some or all of it first. A succinct structure never does that: the compact encoding is the queryable structure. This lesson builds the two ideas that make this possible for sequence data: a bitvector that supports rank and select in essentially constant time using only a small amount of extra space, and the wavelet tree, which uses rank/select on bitvectors to answer rich order-statistic and frequency queries over an entire sequence drawn from a small alphabet.

2. Prerequisites

This lesson builds directly on Bit Manipulation: Core Tricks and Interview Patterns, especially popcount (counting set bits in a word) and basic bit tests/masks. Rank on a bitvector is, at its core, "popcount up to a position," so if Kernighan's popcount trick and bitmasking are unfamiliar, read that lesson first — it is not re-derived here.

3. Core Insight: Rank and Select on Bitvectors

The naive way to answer rank(i) instantly is to precompute a running popcount for every position: an array P where P[i] holds the number of 1-bits in positions $[0, i]$. That gives $O(1)$ rank, but each entry must hold a count up to $n$, needing $\lceil \log_2(n+1) \rceil$ bits, so the whole array costs $O(n \log n)$ bits — often more space than the original bitvector itself. That defeats the purpose of a succinct structure.

The classic fix is a two-level index. Split the bitvector into large superblocks and, inside each superblock, smaller blocks:

• A superblock array stores the absolute rank at the start of each superblock. Since these values run up to $n$, each entry costs $O(\log n)$ bits, but there are only $n / (\log n)^2$ superblocks (choosing superblock size $\Theta((\log n)^2)$), so this array costs $O(n / \log n)$ bits — already $o(n)$.
• A block array stores, for each block inside a superblock, the rank relative to the start of its superblock. Because a block's relative rank is bounded by the superblock size, $\Theta((\log n)^2)$, each entry needs only $O(\log \log n)$ bits, and with block size $\Theta(\log n)$ there are $n / \log n$ blocks — another $o(n)$ bits.
• The remaining offset inside a single $\Theta(\log n)$-bit block is answered with a popcount of a masked machine word — the same trick from the bit-manipulation prerequisite — taking $O(1)$ time on a word-RAM machine.

Add the three pieces together and rank(i) is answered in $O(1)$ time using only $o(n)$ extra bits on top of the $n$ bits of the bitvector itself — asymptotically free, and dramatically less than the naive $O(n \log n)$-bit prefix array. The implementation below uses a simplified single-level block array (fixed-size blocks, no separate superblock tier) for clarity: it still gives $O(1)$ rank in $O(1)$ words per block, but its extra space is $O(n)$ bits rather than the full scheme's $o(n)$ bits. The two-level scheme above is what a production succinct library actually implements.

select(k) has two common answers. The approachable one, implemented below, does a binary search over the same rank/block index to find which block contains the $k$-th one-bit, then scans linearly within that one block, giving $O(\log(n / \text{block size}))$ time using no extra structure beyond the rank index. The alternative for true $O(1)$ select is a separate precomputed structure (for example, sampling every $c$-th one-bit's absolute position directly), which trades additional space for dropping the binary search.

4. A Concrete Example

5. Rank/Select Implementation

The implementation below precomputes the single-level block-rank array from the worked example (block size 4, generalizable to any block size) and answers rank1 in $O(1)$ by combining the block's precomputed rank with a popcount of the remaining bits, and select1 by binary-searching the block-rank array followed by a linear scan inside one block. Both panels reproduce the exact values traced by hand above.

class BitVector:
    """Bitvector with O(1) rank via a precomputed block-rank array, and
    O(log(n / block_size)) select via binary search over that same array."""

    def __init__(self, bits, block_size=4):
        self.n = len(bits)
        self.bits = bits[:]
        self.block_size = block_size
        num_blocks = (self.n + block_size - 1) // block_size + 1
        # block_rank[k] = number of 1-bits in positions [0, k*block_size)
        self.block_rank = [0] * num_blocks
        ones_so_far = 0
        for k in range(1, num_blocks):
            start = (k - 1) * block_size
            end = min(start + block_size, self.n)
            ones_so_far += sum(self.bits[start:end])
            self.block_rank[k] = ones_so_far

    def rank1(self, i):
        """Number of 1-bits in bits[0..i] inclusive. rank1(-1) = 0."""
        if i < 0:
            return 0
        block = i // self.block_size
        start = block * self.block_size
        return self.block_rank[block] + sum(self.bits[start:i + 1])

    def rank0(self, i):
        """Number of 0-bits in bits[0..i] inclusive."""
        if i < 0:
            return 0
        return (i + 1) - self.rank1(i)

    def select1(self, k):
        """Position of the k-th 1-bit, 1-indexed."""
        lo, hi = 0, len(self.block_rank) - 1
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if self.block_rank[mid] < k:
                lo = mid
            else:
                hi = mid - 1
        remaining = k - self.block_rank[lo]
        start = lo * self.block_size
        end = min(start + self.block_size, self.n)
        for pos in range(start, end):
            if self.bits[pos] == 1:
                remaining -= 1
                if remaining == 0:
                    return pos
        raise IndexError("select1: k exceeds number of 1-bits")


bits = [1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1]
bv = BitVector(bits, block_size=4)
print("rank1(5):", bv.rank1(5))      # rank1(5): 3
print("rank1(9):", bv.rank1(9))      # rank1(9): 6
print("select1(5):", bv.select1(5))  # select1(5): 8

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

class BitVector {
public:
    explicit BitVector(const std::vector<int>& bitsIn, int blockSizeIn = 4)
        : bits(bitsIn), blockSize(blockSizeIn), n(static_cast<int>(bitsIn.size())) {
        int numBlocks = (n + blockSize - 1) / blockSize + 1;
        blockRank.assign(numBlocks, 0);
        int onesSoFar = 0;
        for (int k = 1; k < numBlocks; ++k) {
            int start = (k - 1) * blockSize;
            int end = std::min(start + blockSize, n);
            for (int pos = start; pos < end; ++pos) onesSoFar += bits[pos];
            blockRank[k] = onesSoFar;
        }
    }

    // Number of 1-bits in bits[0..i] inclusive; rank1(-1) = 0 by convention.
    int rank1(int i) const {
        if (i < 0) return 0;
        int block = i / blockSize;
        int start = block * blockSize;
        int count = blockRank[block];
        for (int pos = start; pos <= i; ++pos) count += bits[pos];
        return count;
    }

    int rank0(int i) const {
        if (i < 0) return 0;
        return (i + 1) - rank1(i);
    }

    // Position of the k-th 1-bit, 1-indexed.
    int select1(int k) const {
        int lo = 0, hi = static_cast<int>(blockRank.size()) - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (blockRank[mid] < k) lo = mid; else hi = mid - 1;
        }
        int remaining = k - blockRank[lo];
        int start = lo * blockSize;
        int end = std::min(start + blockSize, n);
        for (int pos = start; pos < end; ++pos) {
            if (bits[pos] == 1) {
                if (--remaining == 0) return pos;
            }
        }
        throw std::out_of_range("select1: k exceeds number of 1-bits");
    }

private:
    std::vector<int> bits;
    std::vector<int> blockRank;
    int blockSize;
    int n;
};

int main() {
    std::vector<int> bits{1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1};
    BitVector bv(bits, 4);
    std::cout << "rank1(5): " << bv.rank1(5) << '\n';       // rank1(5): 3
    std::cout << "rank1(9): " << bv.rank1(9) << '\n';       // rank1(9): 6
    std::cout << "select1(5): " << bv.select1(5) << '\n';   // select1(5): 8
}

public class BitVector {
    private final int[] bits;
    private final int[] blockRank;
    private final int blockSize;
    private final int n;

    public BitVector(int[] bitsIn, int blockSizeIn) {
        bits = bitsIn;
        blockSize = blockSizeIn;
        n = bits.length;
        int numBlocks = (n + blockSize - 1) / blockSize + 1;
        blockRank = new int[numBlocks];
        int onesSoFar = 0;
        for (int k = 1; k < numBlocks; k++) {
            int start = (k - 1) * blockSize;
            int end = Math.min(start + blockSize, n);
            for (int pos = start; pos < end; pos++) onesSoFar += bits[pos];
            blockRank[k] = onesSoFar;
        }
    }

    // Number of 1-bits in bits[0..i] inclusive; rank1(-1) = 0 by convention.
    public int rank1(int i) {
        if (i < 0) return 0;
        int block = i / blockSize;
        int start = block * blockSize;
        int count = blockRank[block];
        for (int pos = start; pos <= i; pos++) count += bits[pos];
        return count;
    }

    public int rank0(int i) {
        if (i < 0) return 0;
        return (i + 1) - rank1(i);
    }

    // Position of the k-th 1-bit, 1-indexed.
    public int select1(int k) {
        int lo = 0, hi = blockRank.length - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (blockRank[mid] < k) lo = mid; else hi = mid - 1;
        }
        int remaining = k - blockRank[lo];
        int start = lo * blockSize;
        int end = Math.min(start + blockSize, n);
        for (int pos = start; pos < end; pos++) {
            if (bits[pos] == 1) {
                remaining--;
                if (remaining == 0) return pos;
            }
        }
        throw new IndexOutOfBoundsException("select1: k exceeds number of 1-bits");
    }

    public static void main(String[] args) {
        int[] bits = {1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1};
        BitVector bv = new BitVector(bits, 4);
        System.out.println("rank1(5): " + bv.rank1(5));       // rank1(5): 3
        System.out.println("rank1(9): " + bv.rank1(9));       // rank1(9): 6
        System.out.println("select1(5): " + bv.select1(5));   // select1(5): 8
    }
}

6. Wavelet Trees & the Wavelet Matrix

From Bitvectors to Succinct Sequences

Rank/select on a single bitvector answers questions about a sequence of two symbols, 0 and 1. Real sequences usually range over a larger alphabet — DNA bases, byte values, dictionary ranks of words. The simplest generalization is one bitvector per character: for an alphabet of size $\sigma$, keep $\sigma$ bitvectors, one per symbol, each marking which positions hold that symbol. rank and select for symbol $c$ then reduce to rank/select on bitvector $c$ alone — for example, over the alphabet {A, C, G, T}, a query "how many Gs appear before position 100?" is exactly rank1(99) on the G-bitvector. This works, but storing $\sigma$ full-length bitvectors costs $O(n\sigma)$ bits, which is wasteful for anything beyond a tiny alphabet. The wavelet tree fixes this by sharing bits across symbols through a recursive split of the alphabet rather than one bitvector per character.

Core Insight: Recursive Alphabet Partitioning

Build proceeds top-down: at a node covering alphabet $[lo, hi]$ with $mid = \lfloor (lo+hi)/2 \rfloor$, build a bitvector where bit $i$ is 0 if the $i$-th element (among elements reaching this node, in original relative order) is $\le mid$, else 1. The elements with bit 0 form the left child's sequence over alphabet $[lo, mid]$; the elements with bit 1 form the right child's sequence over $[mid+1, hi]$. Recursion stops at a leaf where $lo = hi$: every element reaching that leaf equals that single value, so no bitvector is needed there.

To answer range k-th smallest (the value that would be $k$-th in sorted order among positions $[l, r]$) at a node with bitvector bv: count how many of positions $[l, r]$ went left, zeros = bv.rank0(r) - bv.rank0(l-1). If $k \le \text{zeros}$, the answer lives in the left child; remap the range into the left child's own indexing via bv.rank0(l-1) and bv.rank0(r)-1, and recurse with the same $k$. Otherwise the answer is in the right child; remap via bv.rank1 instead, and recurse with $k - \text{zeros}$. At a leaf, the answer is simply that leaf's alphabet value.

class BitVector:  # identical to the Section 5 implementation
    def __init__(self, bits, block_size=4):
        self.n = len(bits)
        self.bits = bits[:]
        self.block_size = block_size
        num_blocks = (self.n + block_size - 1) // block_size + 1
        self.block_rank = [0] * num_blocks
        ones_so_far = 0
        for k in range(1, num_blocks):
            start = (k - 1) * block_size
            end = min(start + block_size, self.n)
            ones_so_far += sum(self.bits[start:end])
            self.block_rank[k] = ones_so_far

    def rank1(self, i):
        if i < 0:
            return 0
        block = i // self.block_size
        start = block * self.block_size
        return self.block_rank[block] + sum(self.bits[start:i + 1])

    def rank0(self, i):
        if i < 0:
            return 0
        return (i + 1) - self.rank1(i)


class WaveletTree:
    """Recursively partitions alphabet [lo, hi] in half. Each internal node
    stores a bitvector marking, for the elements that reach it, which half
    of the remaining alphabet each element belongs to."""

    def __init__(self, sequence, lo, hi):
        self.lo, self.hi = lo, hi
        if lo == hi:
            self.bv = self.left = self.right = None
            return
        mid = (lo + hi) // 2
        bits = [0 if value <= mid else 1 for value in sequence]
        self.bv = BitVector(bits, block_size=4)
        left_seq = [value for value in sequence if value <= mid]
        right_seq = [value for value in sequence if value > mid]
        self.left = WaveletTree(left_seq, lo, mid)
        self.right = WaveletTree(right_seq, mid + 1, hi)

    def range_kth_smallest(self, l, r, k):
        """1-indexed k-th smallest value among original positions [l, r]."""
        if self.lo == self.hi:
            return self.lo
        zeros_in_range = self.bv.rank0(r) - self.bv.rank0(l - 1)
        if k <= zeros_in_range:
            new_l = self.bv.rank0(l - 1)
            new_r = self.bv.rank0(r) - 1
            return self.left.range_kth_smallest(new_l, new_r, k)
        new_l = self.bv.rank1(l - 1)
        new_r = self.bv.rank1(r) - 1
        return self.right.range_kth_smallest(new_l, new_r, k - zeros_in_range)


sequence = [2, 1, 3, 1, 2, 4, 3, 2]
tree = WaveletTree(sequence, lo=1, hi=4)
print(tree.range_kth_smallest(1, 5, 3))  # 3rd smallest of [1,3,1,2,4] -> 2
print(tree.range_kth_smallest(0, 7, 1))  # smallest of the whole array -> 1

#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>

class BitVector {  // identical to the Section 5 implementation
public:
    explicit BitVector(const std::vector<int>& bitsIn, int blockSizeIn = 4)
        : bits(bitsIn), blockSize(blockSizeIn), n(static_cast<int>(bitsIn.size())) {
        int numBlocks = (n + blockSize - 1) / blockSize + 1;
        blockRank.assign(numBlocks, 0);
        int onesSoFar = 0;
        for (int k = 1; k < numBlocks; ++k) {
            int start = (k - 1) * blockSize;
            int end = std::min(start + blockSize, n);
            for (int pos = start; pos < end; ++pos) onesSoFar += bits[pos];
            blockRank[k] = onesSoFar;
        }
    }

    int rank1(int i) const {
        if (i < 0) return 0;
        int block = i / blockSize;
        int start = block * blockSize;
        int count = blockRank[block];
        for (int pos = start; pos <= i; ++pos) count += bits[pos];
        return count;
    }

    int rank0(int i) const {
        if (i < 0) return 0;
        return (i + 1) - rank1(i);
    }

private:
    std::vector<int> bits;
    std::vector<int> blockRank;
    int blockSize;
    int n;
};

class WaveletTree {
public:
    WaveletTree(const std::vector<int>& sequence, int lo, int hi) : lo(lo), hi(hi) {
        if (lo == hi) return;  // leaf: no bitvector, no children
        int mid = (lo + hi) / 2;
        std::vector<int> bits, leftSeq, rightSeq;
        for (int value : sequence) {
            if (value <= mid) {
                bits.push_back(0);
                leftSeq.push_back(value);
            } else {
                bits.push_back(1);
                rightSeq.push_back(value);
            }
        }
        bv = std::make_unique<BitVector>(bits, 4);
        left = std::make_unique<WaveletTree>(leftSeq, lo, mid);
        right = std::make_unique<WaveletTree>(rightSeq, mid + 1, hi);
    }

    // 1-indexed k-th smallest value among original positions [l, r].
    int rangeKthSmallest(int l, int r, int k) const {
        if (lo == hi) return lo;
        int zerosInRange = bv->rank0(r) - bv->rank0(l - 1);
        if (k <= zerosInRange) {
            int newL = bv->rank0(l - 1);
            int newR = bv->rank0(r) - 1;
            return left->rangeKthSmallest(newL, newR, k);
        }
        int newL = bv->rank1(l - 1);
        int newR = bv->rank1(r) - 1;
        return right->rangeKthSmallest(newL, newR, k - zerosInRange);
    }

private:
    int lo, hi;
    std::unique_ptr<BitVector> bv;
    std::unique_ptr<WaveletTree> left, right;
};

int main() {
    std::vector<int> sequence{2, 1, 3, 1, 2, 4, 3, 2};
    WaveletTree tree(sequence, 1, 4);
    std::cout << tree.rangeKthSmallest(1, 5, 3) << '\n';  // 2
    std::cout << tree.rangeKthSmallest(0, 7, 1) << '\n';  // 1
}

import java.util.ArrayList;
import java.util.List;

public class WaveletTree {
    static class BitVector {  // identical to the Section 5 implementation
        private final int[] bits;
        private final int[] blockRank;
        private final int blockSize;

        BitVector(int[] bitsIn, int blockSizeIn) {
            bits = bitsIn;
            blockSize = blockSizeIn;
            int n = bits.length;
            int numBlocks = (n + blockSize - 1) / blockSize + 1;
            blockRank = new int[numBlocks];
            int onesSoFar = 0;
            for (int k = 1; k < numBlocks; k++) {
                int start = (k - 1) * blockSize;
                int end = Math.min(start + blockSize, n);
                for (int pos = start; pos < end; pos++) onesSoFar += bits[pos];
                blockRank[k] = onesSoFar;
            }
        }

        int rank1(int i) {
            if (i < 0) return 0;
            int block = i / blockSize;
            int start = block * blockSize;
            int count = blockRank[block];
            for (int pos = start; pos <= i; pos++) count += bits[pos];
            return count;
        }

        int rank0(int i) {
            if (i < 0) return 0;
            return (i + 1) - rank1(i);
        }
    }

    private final int lo, hi;
    private BitVector bv;
    private WaveletTree left, right;

    WaveletTree(List<Integer> sequence, int lo, int hi) {
        this.lo = lo;
        this.hi = hi;
        if (lo == hi) return;  // leaf

        int mid = (lo + hi) / 2;
        int[] bits = new int[sequence.size()];
        List<Integer> leftSeq = new ArrayList<>();
        List<Integer> rightSeq = new ArrayList<>();
        for (int idx = 0; idx < sequence.size(); idx++) {
            int value = sequence.get(idx);
            if (value <= mid) {
                bits[idx] = 0;
                leftSeq.add(value);
            } else {
                bits[idx] = 1;
                rightSeq.add(value);
            }
        }
        bv = new BitVector(bits, 4);
        left = new WaveletTree(leftSeq, lo, mid);
        right = new WaveletTree(rightSeq, mid + 1, hi);
    }

    // 1-indexed k-th smallest value among original positions [l, r].
    int rangeKthSmallest(int l, int r, int k) {
        if (lo == hi) return lo;
        int zerosInRange = bv.rank0(r) - bv.rank0(l - 1);
        if (k <= zerosInRange) {
            int newL = bv.rank0(l - 1);
            int newR = bv.rank0(r) - 1;
            return left.rangeKthSmallest(newL, newR, k);
        }
        int newL = bv.rank1(l - 1);
        int newR = bv.rank1(r) - 1;
        return right.rangeKthSmallest(newL, newR, k - zerosInRange);
    }

    public static void main(String[] args) {
        List<Integer> sequence = List.of(2, 1, 3, 1, 2, 4, 3, 2);
        WaveletTree tree = new WaveletTree(sequence, 1, 4);
        System.out.println(tree.rangeKthSmallest(1, 5, 3));  // 2
        System.out.println(tree.rangeKthSmallest(0, 7, 1));  // 1
    }
}

Rank of a Value and Range Frequency

The other two flagship wavelet-tree queries follow the exact same recursive remapping, just steered differently. For rank of value $v$ in range $[l, r]$ ("how many times does $v$ occur in positions $[l,r]$?"), descend by comparing $v$ against each node's $mid$ instead of comparing counts: go left if $v \le mid$, right otherwise, remapping $[l,r]$ with rank0/rank1 exactly as before. At the leaf $lo = hi = v$, the answer is simply the size of the remapped range, $r - l + 1$:

def count_value_in_range(node, l, r, v):
    if l > r:
        return 0
    if node.lo == node.hi:
        return r - l + 1
    if v <= (node.lo + node.hi) // 2:
        new_l, new_r = node.bv.rank0(l - 1), node.bv.rank0(r) - 1
        return count_value_in_range(node.left, new_l, new_r, v)
    new_l, new_r = node.bv.rank1(l - 1), node.bv.rank1(r) - 1
    return count_value_in_range(node.right, new_l, new_r, v)

Range frequency for a value range $[v_{lo}, v_{hi}]$ (rather than a single value) generalizes this further: descend both children whenever $[v_{lo}, v_{hi}]$ straddles a node's $mid$, adding the fully-covered child's remapped range size directly and recursing only into the partially-covered side, again using nothing but rank0/rank1. Every one of these queries costs $O(\log \sigma)$ node visits, each doing $O(1)$ rank work — the wavelet tree turns rank/select on bits into rank/select on an arbitrary alphabet.

Wavelet Matrix: A Flattened Alternative

The wavelet tree stores one smaller bitvector per node, with the sequence physically split and re-partitioned into ever-smaller arrays at each level — a pointer-heavy structure that mirrors a balanced BST. The wavelet matrix stores the exact same information differently: one bitvector per alphabet-bit level (so $\lceil \log_2 \sigma \rceil$ bitvectors total), each the full length of the original sequence, rather than a tree of progressively smaller node-local bitvectors. Instead of physically partitioning the sequence into child arrays, the matrix keeps every level's bits in the same flat array and uses a stable partition (0s before 1s) to derive each subsequent level's ordering implicitly, tracked via small per-level offset counters rather than explicit tree pointers.

The two structures answer identical queries with identical asymptotic complexity — they are conceptually equivalent, level-by-level unrollings of the same recursive alphabet split. The matrix wins in practice because it is one flat array of bitvectors instead of a heap-allocated tree of small ones: better cache locality (no pointer chasing between nodes), less memory overhead (no per-node object headers), and a simpler, iterative (not recursive) implementation. This is why production succinct-data-structure libraries (such as SDSL and the succinct/sux family) implement wavelet matrices, not wavelet trees, despite teaching the tree first because its recursive structure is easier to reason about.

7. FM-Index Foundations

The FM-index is the classic application that made rank/select on bitvectors famous: it supports substring search — "does pattern $P$ occur in text $T$, and where?" — using space close to the compressed size of $T$, not the original size. It combines two ideas: the Burrows–Wheeler Transform (BWT), which permutes $T$'s characters into an order that clusters repeated contexts together (making the result highly compressible), and rank/select on the transformed string, computed per-character exactly as described in this lesson's "sequence of bitvectors" view (or, at larger alphabets, via a wavelet tree/matrix over the transformed string's alphabet).

Search proceeds backward, one pattern character at a time, using a technique called LF-mapping: at each step, a constant number of rank queries on the BWT narrows a range of matching positions, without ever touching the original text. After processing all of $P$, the size of the final range is the number of occurrences, and each occurrence's original position can be recovered via periodic sampling plus more rank/select steps.

Building the actual BWT requires constructing a suffix array (or an equivalent structure) for $T$, which is a substantial topic of its own and is out of scope here. Treat this section as a pointer to where rank/select structures lead next: a later, more advanced string-algorithms curriculum entry is the right place for the full BWT-construction-to-FM-index treatment.

8. Complexity Analysis

9. Applications & Alternatives

10. Exercises & Mastery

Easy

1. Given that select is already implemented, implement rank(i) on the 16-bit bitvector 1011 0010 1101 0001 by hand or code, without a precomputed block array — just by scanning and counting — then check your answer against the block-based rank1 from Section 5.

Medium

1. Using the wavelet tree built over sequence = [2, 1, 3, 1, 2, 4, 3, 2] (alphabet $[1,4]$) from Section 6, implement a range-frequency query: how many times does value 2 appear in positions $[0, 7]$? Verify your traversal against a direct linear scan of the array.

Hard

1. Build a wavelet tree over the new array [6, 2, 5, 2, 6, 3, 1, 5, 3, 1] (alphabet $[1,6]$), and trace the full recursion path — the alphabet split at each node, the resulting bitvector, and the remapped range at each level — to answer "what is the 4th smallest value in positions $[2, 8]$?" by hand before checking it against code.

Review rhythm: tomorrow, reconstruct the block-rank array and the rank/select formulas from memory; next week, re-derive the wavelet tree's range remapping (rank0/rank1 on $[l-1]$ and $[r]$) without looking it up; several weeks later, recognize the same "recurse on a balanced split of the value domain, not the position domain" idea in a new problem, such as a merge-sort tree or a persistent segment tree over values. Finally, teach someone the difference between "succinct" and "compressed" using the FM-index as the motivating example.

11. Summary Cheat Sheet

• Succinct means space close to the information-theoretic minimum while still supporting fast direct queries — not merely small.
• rank(i) counts 1-bits in $[0,i]$; select(k) finds the position of the $k$-th 1-bit.
• A two-level superblock/block index gives $O(1)$ rank using only $o(n)$ extra bits; a single-level block array (implemented here) gives $O(1)$ rank using $O(n)$ extra bits — both far cheaper than a naive $O(n \log n)$-bit prefix array.
• select can binary-search the rank index in $O(\log(n/\text{block size}))$, or use a dedicated sampled structure for $O(1)$.
• A wavelet tree recursively splits the alphabet in half; each node's bitvector routes elements to the correct child using only rank/select.
• Range k-th-smallest, rank-of-value, and range-frequency all cost $O(\log \sigma)$ using $O(n \log \sigma)$ bits total.
• A wavelet matrix stores the same information as one flat bitvector per alphabet-bit level instead of a tree of node-local bitvectors — same queries, better cache locality, and what real libraries actually ship.
• The FM-index layers BWT plus rank/select on the transformed string to search compressed text directly; full construction needs a suffix array and is covered elsewhere.