Wavelet Trees

Imagine a long sequence of characters drawn from an alphabet — say, the DNA string ACGTACGTACGT, or a million integers from 1 to 1000. You want to answer queries like:

• Rank: how many times does the letter G appear in the first 7 positions?
• Select: where is the 3rd occurrence of C?
• k-th smallest: what is the 4th smallest value in positions 5 through 10?

You could sort for some queries and keep a separate inverted index for others. Or you could build a single wavelet tree — a structure invented by Grossi, Gupta and Vitter in 2003 — and answer all of them in $O(\log \sigma)$ time, where $\sigma$ is the alphabet size, using space very close to the information-theoretic lower bound.

The key idea is binary recursion: split the alphabet in half, record for each position whether its symbol belongs to the lower or upper half (one bit per position), then recurse on the two sub-sequences. Each level of the tree is just a bit-vector supporting rank and select in $O(1)$ after preprocessing — and $\log_2 \sigma$ levels is all you need to identify any symbol.

It sounds almost too simple. The remarkable part is how many apparently unrelated queries collapse into a handful of rank/select calls on those bit-vectors.

Below is a small integer sequence. The demo builds a wavelet tree over it and lets you ask for the k-th smallest value in any range [l, r]. Each step shows which sub-tree the algorithm descends into and why.

<p class="hint">{{hint}}</p>
<div class="seq-row" id="seqRow"></div>
<div class="controls">
  <label>l (1-based): <input id="inL" type="number" min="1" max="16" value="2"></label>
  <label>r: <input id="inR" type="number" min="1" max="16" value="10"></label>
  <label>k: <input id="inK" type="number" min="1" max="16" value="3"></label>
  <button id="btnFind" type="button">{{btn_find}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="treeArea"></div>
<div class="result" id="result"></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; }
.seq-row { display: flex; gap: 3px; flex-wrap: wrap; margin-bottom: .6rem; }
.seq-cell { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
            font: 700 13px ui-monospace, monospace; border-radius: 6px;
            background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; }
.seq-cell.in-range { background: #b8d4ec; border-color: #6fa8c8; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .85rem; color: #444; }
input[type=number] { width: 48px; margin-left: 4px; padding: 3px 5px; border: 1px solid #cdd9e3;
                     border-radius: 5px; font-size: .85rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#treeArea { margin-top: .3rem; }
.level-label { font: 600 12px system-ui; color: #666; margin: .4rem 0 .15rem; }
.level-row { display: flex; gap: 3px; flex-wrap: wrap; }
.bit-cell { width: 26px; height: 26px; display: flex; align-items: center; justify-content: center;
            font: 700 11px ui-monospace, monospace; border-radius: 4px;
            background: #f0f0f0; border: 1px solid #d0d0d0; color: #555; }
.bit-cell.lo { background: #dbeafe; border-color: #93c5fd; color: #1e40af; }
.bit-cell.hi { background: #fce7f3; border-color: #f9a8d4; color: #9d174d; }
.bit-cell.active { outline: 2px solid #f97316; outline-offset: 1px; }
.sep { width: 8px; }
.result { margin-top: .6rem; font: 700 1rem system-ui; min-height: 1.4em; }
.result.ok { color: #0a7d33; }
.result.err { color: #c92f3c; }

// Code not found

Notice the asymmetry: building the tree is a one-time $O(n \log \sigma)$ cost, but each query afterwards costs only $O(\log \sigma)$ steps regardless of how long the sequence is. The tree does not store the actual symbols at each node — only bits — yet those bits are enough to navigate to any answer.

How good is a wavelet tree, precisely?

• Query time: every rank, select or k-th-smallest query descends one path from root to leaf through $\log_2 \sigma$ levels. At each level it calls rank or select on a bit-vector, which takes $O(1)$ with standard preprocessing (Jacobson, 1989). Total: $O(\log \sigma)$ per query.
• Space: the tree has $\log_2 \sigma$ levels, each storing $n$ bits — so $n \log_2 \sigma$ bits in total. With careful encoding this reaches $nH_0 + o(n \log \sigma)$ bits, where $H_0$ is the zeroth-order empirical entropy of the sequence. For highly repetitive sequences, compressed wavelet trees get much closer to $nH_k$ (higher-order entropy).
• Build time: $O(n \log \sigma)$ — scan $n$ symbols at each of the $\log_2 \sigma$ levels.
• What it supports: in a single structure — rank, select, access (retrieve the $i$-th symbol), range frequency (count occurrences of any symbol or range of symbols in $[l,r]$), k-th smallest in $[l,r]$, and several geometric queries on point grids.

The structure was introduced by Grossi, Gupta and Vitter (2003) as part of compressed suffix arrays. The name wavelet tree comes from the analogy with wavelet decompositions: each level separates "low-frequency" from "high-frequency" symbols, just as a wavelet transform separates frequency bands. Compressed variants and practical engineering are surveyed in Navarro's "Wavelet Trees for All" (2014).

For comparison: supporting range frequency naively requires one array per symbol ($O(\sigma n)$ space total); binary search on sorted arrays answers k-th smallest but not rank. The wavelet tree dissolves both limitations at once. See pattern matching for a related setting where similar succinct ideas appear.

"Answer many query types at once, in near-optimal space" is the core promise, and it turns out to be useful almost everywhere sequences appear:

• Compressed full-text search: the FM-index (used in BWA, Bowtie and other genome aligners) uses a wavelet tree to support the backward-search step on the Burrows-Wheeler transform in $O(\log \sigma)$ per character. This lets you search a 3-billion-base human genome in gigabytes of RAM instead of tens of gigabytes.
• Genomics and bioinformatics: VCF files, pangenome graphs and RNA-seq pipelines all contain large sequences over small or medium alphabets. Wavelet trees allow counting, locating and extracting subsequences without decompressing.
• Column stores and analytics: a database column of integers or categories can be stored as a wavelet tree, supporting range-aggregate queries (count how many values fall in $[a,b]$ within rows $[l,r]$) directly on the compressed representation.
• Computational geometry: a wavelet tree over $y$-coordinates of points sorted by $x$ answers 2-D dominance counting and orthogonal range reporting, replacing heavier range trees.
• Information retrieval: inverted indexes for ranked retrieval can be replaced or augmented with wavelet trees when the vocabulary is bounded and rank/select over postings lists is needed.

Learn how a wavelet tree works and you've gained a lens that makes dozens of "specialised" data structures look like special cases of one clean recursive idea. Compare with sequence alignment for another context where succinct representations of sequences matter.

A wavelet tree is built from an almost embarrassingly simple idea: split the alphabet in two, write one bit per position, and recurse. Yet that idea, applied $\log_2 \sigma$ times, produces a structure that can answer rank, select, access, range frequency, k-th smallest and several geometric queries — all in $O(\log \sigma)$ time — while using space within a small factor of the information-theoretic minimum.

The next time you face a sequence problem that seems to demand several specialised indexes at once, ask whether the alphabet is bounded. If it is, a wavelet tree may turn a handful of apparently different problems into a single clean structure — and give you the answer in the time it takes to read $\log_2 \sigma$ bits.