↩ back to Array-Backed Trees

Wavelet Tree

Every tree-shaped structure elsewhere in this site's Array-Backed Trees category splits an array by position — a segment tree's left half is the first half of the indices, full stop. A wavelet tree splits by value instead: every element of a sequence drawn from a small alphabet {0, ..., σ-1} gets routed left or right depending on whether it's in the lower or upper half of the current alphabet range, and that one idea, applied recursively, answers three questions in O(log σ) — not O(log n), and usually much smaller, since the alphabet is often far smaller than the sequence: access(i) (what symbol sits at position i), rank(c, i) (how many times symbol c appears before position i), and select(c, k) (where the k-th occurrence of symbol c sits).

Try it

The sequence below has 12 symbols drawn from an 8-symbol alphabet (0-7), so the tree has exactly ⌈log₂ 8⌉ = 3 levels. At the root, every symbol ≤ mid (here mid = 3) is routed left, every symbol > mid routed right — recorded as one bit per position, 0 for left and 1 for right. Each child repeats the split on its own narrower half of the alphabet, over its own already-filtered sub-sequence, until the alphabet range narrows to a single symbol. The top row always shows the full original sequence — shaded positions are still "in play" at the current node, faded ones already routed elsewhere; the panel below it shows that node's own compact values-and-bits view. Pick an operation, Load it, then step through to see exactly which level's bit row gets consulted and how the position (or count) translates to the next level down — or, for select, back up.

Why it works

The recursive alphabet split. A node covering alphabet range [lo, hi] stores the sub-sequence of elements routed to it, a mid = ⌊(lo+hi)/2⌋, and one bit per element of that sub-sequence — 0 if the element is ≤ mid, 1 otherwise. The 0-bit elements, in their original relative order, become the left child's sub-sequence over [lo, mid]; the 1-bit elements become the right child's over [mid+1, hi]. Recursing stops once lo === hi — a leaf holds every occurrence of exactly one symbol. On this page's demo, the root's bits for [4,1,3,7,0,5,2,6,4,1,3,5] against mid=3 are [1,0,0,1,0,1,0,1,1,0,0,1] — the left child's sub-sequence becomes [1,3,0,2,1,3] (alphabet [0,3]), the right child's [4,7,5,6,4,5] (alphabet [4,7]), each splitting again one level down.

Access descends once per level, translating position as it goes. To find the symbol at position i: read bit = node.bits[i], then move to the matching child at the position rank(bit, i) — the count of that same bit value among node.bits[0, i). That's the position i's element lands at inside the child's own, shorter sub-sequence, because the child's sub-sequence is exactly the elements that share this bit, in the same relative order. Repeat until a leaf is reached; the leaf's single symbol is the answer. On the demo, access(5) (value 5) takes exactly 3 steps: root bit 1 at position 5 (2 ones before it) → right child, position 2; that node's bit 0 at position 2 (1 zero before it) → its left child, position 1; that node's bit 1 at position 1 (0 ones before it) → the leaf for symbol 5, position 0 — done.

Rank threads a count through the same descent, not a position. To count occurrences of c before position i: at each node, decide which child c itself belongs in (c ≤ mid → left, else right — a comparison against the alphabet range, unrelated to any particular element), then descend into that child at position rank(bit, i), the same translation access uses, but computed for the bit c would have rather than any element actually at position i. Whatever count survives to the leaf holding c is the answer, because every element that reached that leaf is an occurrence of c by construction — counting positions there is exactly counting occurrences. rank(4, 9) on the demo: root, 4 > mid(3) → right, translate 9 → 5; next node, 4 ≤ mid(5) → left, translate 5 → 3; next node, 4 ≤ mid(4) → left, translate 3 → 2; leaf for 4 → answer 2, matching the two 4s sitting at indices 0 and 8 in the original sequence.

Select runs the whole thing backwards — down to find the leaf, then up to recover the position. Descending from the root to the leaf for c needs no data at all, only alphabet-range comparisons, so it just records which branch (left/right) was taken at each level. The k-th occurrence of c is then simply local index k-1 within that leaf. Climbing back up one level at a time, a local index p becomes posbit[p] in the parent — the position of the p-th (0-indexed) occurrence of whichever bit led to the child just left, precomputed once per node alongside the rank prefix table. After unwinding all the way to the root, p is the answer, a real index into the original sequence. This is the mirror image of rank: rank turns a position into a count by descending; select turns a count back into a position by descending to find the leaf and then ascending to reconstruct it.

Reference implementation

class WaveletTree {
  constructor(lo, hi, seq) {
    this.lo = lo;
    this.hi = hi;
    this.seq = seq;                    // the sub-sequence this node is responsible for
    if (lo === hi) { this.leaf = true; return; }
    this.leaf = false;
    this.mid = Math.floor((lo + hi) / 2);
    this.bits = seq.map((v) => (v <= this.mid ? 0 : 1));
    this.prefix0 = [0];                // prefix0[i] = count of 0s in bits[0, i)
    for (let i = 0; i < this.bits.length; i++) {
      this.prefix0.push(this.prefix0[i] + (this.bits[i] === 0 ? 1 : 0));
    }
    this.pos0 = []; this.pos1 = [];    // pos_b[k] = local index of the k-th (0-indexed) bit === b
    this.bits.forEach((b, i) => (b === 0 ? this.pos0 : this.pos1).push(i));
    this.left = new WaveletTree(lo, this.mid, seq.filter((v) => v <= this.mid));
    this.right = new WaveletTree(this.mid + 1, hi, seq.filter((v) => v > this.mid));
  }

  rankBit(b, i) { return b === 0 ? this.prefix0[i] : i - this.prefix0[i]; }

  access(i) {
    if (this.leaf) return this.lo;
    const b = this.bits[i];
    const child = b === 0 ? this.left : this.right;
    return child.access(this.rankBit(b, i));
  }

  rank(c, i) {
    if (this.leaf) return i;
    const b = c <= this.mid ? 0 : 1;
    const child = b === 0 ? this.left : this.right;
    return child.rank(c, this.rankBit(b, i));
  }

  select(c, k) {
    if (k < 1) return null;
    const path = [];
    let node = this;
    while (!node.leaf) {
      const b = c <= node.mid ? 0 : 1;
      path.push([node, b]);
      node = b === 0 ? node.left : node.right;
    }
    if (k > node.seq.length) return null;   // fewer than k occurrences of c exist
    let p = k - 1;
    for (let j = path.length - 1; j >= 0; j--) {
      const [pnode, b] = path[j];
      p = (b === 0 ? pnode.pos0 : pnode.pos1)[p];
    }
    return p;
  }
}

Verified two ways before writing any of the prose above. First, exhaustively: every one of the 16 possible length-4 sequences over a 2-symbol alphabet, access/rank/ select checked at every valid query point against a plain-array reference — 240 checks, 0 mismatches. Second, 5,000 randomized trials with sequence length up to 40 and alphabet size up to 16 (chosen as a power of two each trial), several access/rank/select queries per trial against the same plain-array reference — 156,634 checks, 0 mismatches. The demo's own worked numbers (access(5) = 5, rank(4, 9) = 2, select(1, 2) = 9) come directly from running this exact class, not a hand-traced approximation.

Pitfalls

Rank counts a half-open range, [0, i), not [0, i] — off by one silently double-counts a match sitting exactly at index i. Every rankBit call and every prefix0 lookup in the reference above is written against "count of this bit among the first i positions," and i itself never gets included as a position being counted, only as a boundary. Passing i+1 where i was meant looks harmless in isolation — rank(c, i) still returns some number — but it's the wrong one exactly when seq[i] === c, which a handful of scattered test queries can easily miss.

Select must explicitly guard against a k that doesn't exist for that symbol. On the demo sequence, symbol 6 appears exactly once (index 7): select(6, 1) = 7, but select(6, 2) has no answer at all. Without the k > node.seq.length check at the leaf, the code would read past the end of pos0/pos1 on the way back up and either return undefined silently or crash on the first array index that comes back malformed — neither of which says "there aren't that many occurrences," which is the actual situation.

The complexity bound assumes O(1) rank on each level's bit array, which itself costs real preprocessing. The reference implementation gets there with a prefix0 array (and pos0/pos1 for select) built once per node at construction time — O(n) extra ints per level, O(n log σ) total, exactly matching the structure's own space bound below. A version that instead scans node.bits[0, i) by hand on every call still gets the right answer, but each level costs O(√u) to O(u) depending on that level's own sub-sequence length rather than O(1) — the difference between O(log σ) total and something asymptotically much worse, with nothing in a correctness check able to catch it, the same class of silent regression Van Emde Boas Tree's own pitfalls section describes for its two-recursive-calls bug.

An alphabet size that isn't a power of two makes some leaves shallower than others. This page's demo alphabet (σ = 8) happens to be a perfect power of two, so every leaf sits at depth exactly 3. In general the tree's depth is ⌈log₂ σ⌉, and a mid = ⌊(lo+hi)/2⌋ split on an odd-sized range sends one symbol fewer to one side than the other — the tree stays correct (every query above still works exactly as described), it's simply not perfectly balanced, and a few symbols resolve one comparison faster than the rest.

Complexity

Time: access, rank, and select are all O(log σ) — one O(1) rank-on-a-bit-array step per level, and ⌈log₂ σ⌉ levels total, independent of the sequence length n. Building the tree costs O(n log σ): each of the ⌈log₂ σ⌉ levels does O(n) work across all of that level's nodes combined, since every element lives in exactly one node per level. Space: O(n log σ) bits for this reference implementation — each of the n elements contributes exactly one bit per level it passes through, plus the O(n)-per-level prefix0/pos0/pos1 tables that make each level's operations O(1) (see Pitfalls).

This site's guide, Choosing a Range Query Structure, sets this entry aside the same way it already sets aside Binary Heap, Mo's Algorithm, and Van Emde Boas Tree — a fourth genuinely different question. The guide's six compared entries all maintain some running answer over a contiguous range of positions in a changing array. A wavelet tree answers questions about values in a fixed sequence — which symbol, how many of a symbol, which occurrence — with a complexity model built around the alphabet size rather than the sequence length, and (in its succinct real-world form, not built here) doubles as the basis for range-quantile and range-value-counting queries that none of the six comparison entries can answer at all. Merge Sort Tree answers that same range-value-counting question — how many values in [l,r] are ≤ x — with plain sorted arrays and a binary search per node instead of a bit-vector per level, simpler code at a real space cost.