The Real Complexity of Wavelet Trees

Introduction

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.

Try It

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">The sequence below is indexed by a wavelet tree. Pick a range <b>[l, r]</b> and a rank <b>k</b>, then press <b>Find k-th Smallest</b> to see the algorithm descend the tree level by level.</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">Find k-th Smallest</button>
  <button id="btnReset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Wavelet tree over a small sequence of integers.
// Supports k-th smallest in range [l,r] in O(log sigma) steps.
// Each node stores a bitvector: 0 = symbol goes to lo child, 1 = hi child.
// To find the k-th smallest in [l,r]:
//   1. Count zeros in [l,r] of the current node's bitvector => lo_count.
//   2. If k <= lo_count, recurse into lo child with the mapped range and k.
//   3. Otherwise recurse into hi child with the mapped range and k - lo_count.
//   4. At a leaf (range of size 1), the answer is that single symbol.

const SEQ = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 2];
const N = SEQ.length; // 16

// Build wavelet tree as array of levels.
// Each level is an array of 0/1 bits (same length as SEQ).
// Parallel: also track the alphabet range [lo, hi] at each level.
// We split [lo, hi] into [lo, mid] and [mid+1, hi].
// The level bitvector: 0 if seq[i] <= mid, else 1.
// After splitting, the order of elements within each half is preserved.

function buildLevels(seq, lo, hi) {
  if (lo >= hi) return [];
  const mid = Math.floor((lo + hi) / 2);
  const bits = seq.map(v => v <= mid ? 0 : 1);
  const loSeq = seq.filter(v => v <= mid);
  const hiSeq = seq.filter(v => v > mid);
  return [{ bits, lo, hi, mid }].concat(
    buildLevels(loSeq, lo, mid),
    buildLevels(hiSeq, mid + 1, hi)
  );
}

// Build a proper tree structure for navigation.
// node = { lo, hi, mid, bits, left, right }
function buildTree(seq, lo, hi) {
  if (lo >= hi) return { lo, hi, leaf: true, value: lo };
  const mid = Math.floor((lo + hi) / 2);
  const bits = seq.map(v => v <= mid ? 0 : 1);
  const loSeq = seq.filter(v => v <= mid);
  const hiSeq = seq.filter(v => v > mid);
  return {
    lo, hi, mid, bits, seq,
    left:  buildTree(loSeq, lo, mid),
    right: buildTree(hiSeq, mid + 1, hi),
    leaf: false
  };
}

const ROOT = buildTree(SEQ, 1, 9);

// Count zeros in bits[l..r] (0-indexed, inclusive)
function countZeros(bits, l, r) {
  let c = 0;
  for (let i = l; i <= r; i++) if (bits[i] === 0) c++;
  return c;
}
// Map position l (0-indexed) in parent seq to child (lo or hi) index.
// lo child: rank of zeros up to l-1 (number of 0s before position l)
function mapToLo(bits, pos) {
  let c = 0;
  for (let i = 0; i < pos; i++) if (bits[i] === 0) c++;
  return c;
}
function mapToHi(bits, pos) {
  let c = 0;
  for (let i = 0; i < pos; i++) if (bits[i] === 1) c++;
  return c;
}

// k-th smallest (1-indexed k) in node.seq[l..r] (0-indexed, inclusive)
// Returns { value, steps } where steps is array of { node, l, r, k, dir }
function kthSmallest(node, l, r, k) {
  const steps = [];
  function go(nd, l, r, k) {
    if (nd.leaf) {
      steps.push({ node: nd, l, r, k, dir: 'leaf' });
      return nd.value;
    }
    const zeros = countZeros(nd.bits, l, r);
    const dir = k <= zeros ? 'lo' : 'hi';
    steps.push({ node: nd, l, r, k, zeros, dir });
    if (dir === 'lo') {
      const nl = mapToLo(nd.bits, l);
      const nr = nl + zeros - 1;
      return go(nd.left, nl, nr, k);
    } else {
      const ones_before_l = mapToHi(nd.bits, l);
      const nl = ones_before_l;
      const nr = nl + (r - l + 1 - zeros) - 1;
      return go(nd.right, nl, nr, k - zeros);
    }
  }
  const value = go(node, l, r, k);
  return { value, steps };
}

// Render the original sequence with range highlighted
function renderSeq(l, r) {
  const row = document.getElementById('seqRow');
  row.innerHTML = '';
  SEQ.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'seq-cell' + (i >= l && i <= r ? ' in-range' : '');
    d.textContent = v;
    row.appendChild(d);
  });
}

// Render tree levels with bits highlighted for active range
function renderTree(steps) {
  const area = document.getElementById('treeArea');
  area.innerHTML = '';
  if (!steps || steps.length === 0) return;

  steps.forEach((step, si) => {
    const nd = step.node;
    if (nd.leaf) {
      const lbl = document.createElement('div');
      lbl.className = 'level-label';
      lbl.textContent = fmt('Step %si%%v%: leaf → answer = %value%', { si: si, v: 1, value: nd.value });
      area.appendChild(lbl);
      return;
    }
    const lbl = document.createElement('div');
    lbl.className = 'level-label';
    const info = step.dir === 'lo'
      ? fmt('zeros in [%l%,%r%] = %zeros% ≥ k=%k% → go LEFT (≤%mid%)', { l: step.l, r: step.r, zeros: step.zeros, k: step.k, mid: nd.mid })
      : fmt('zeros in [%l%,%r%] = %zeros% < k=%k% → go RIGHT (>%mid%)', { l: step.l, r: step.r, zeros: step.zeros, k: step.k, mid: nd.mid });
    lbl.textContent = fmt('Step %si%%v% [%lo%..%hi%]: %info%', { si: si, v: 1, lo: nd.lo, hi: nd.hi, info: info });
    area.appendChild(lbl);

    const row = document.createElement('div');
    row.className = 'level-row';
    nd.bits.forEach((b, i) => {
      if (i > 0 && i === step.l) {
        const sep = document.createElement('div'); sep.className = 'sep'; row.appendChild(sep);
      }
      const d = document.createElement('div');
      const inRange = i >= step.l && i <= step.r;
      d.className = 'bit-cell ' + (b === 0 ? 'lo' : 'hi') + (inRange ? ' active' : '');
      d.textContent = b;
      row.appendChild(d);
      if (i === step.r && step.r < nd.bits.length - 1) {
        const sep = document.createElement('div'); sep.className = 'sep'; row.appendChild(sep);
      }
    });
    area.appendChild(row);
  });
}

function run() {
  const l0 = parseInt(document.getElementById('inL').value, 10) - 1; // 0-indexed
  const r0 = parseInt(document.getElementById('inR').value, 10) - 1;
  const k  = parseInt(document.getElementById('inK').value, 10);
  const res = document.getElementById('result');

  if (isNaN(l0) || isNaN(r0) || isNaN(k) || l0 < 0 || r0 >= N || l0 > r0 || k < 1 || k > r0 - l0 + 1) {
    res.textContent = '⚠ Invalid input. Check that 1 ≤ l ≤ r ≤ 16 and 1 ≤ k ≤ (r−l+1).';
    res.className = 'result err';
    renderSeq(-1, -1); renderTree(null);
    return;
  }
  renderSeq(l0, r0);
  const { value, steps } = kthSmallest(ROOT, l0, r0, k);
  renderTree(steps);
  res.textContent = fmt('The %k%-th smallest value in positions [%l0%%v%, %r0%%v%] is %value%.', { k: k, l0: l0, v: 1, r0: r0, value: value });
  res.className = 'result ok';
  console.log('k-th smallest answer:', value, '| steps:', steps.length);
}

function reset() {
  document.getElementById('inL').value = 2;
  document.getElementById('inR').value = 10;
  document.getElementById('inK').value = 3;
  document.getElementById('treeArea').innerHTML = '';
  document.getElementById('result').textContent = '';
  document.getElementById('result').className = 'result';
  renderSeq(-1, -1);
}

document.getElementById('btnFind').addEventListener('click', run);
document.getElementById('btnReset').addEventListener('click', reset);
renderSeq(-1, -1);

<p class="hint">The sequence below is indexed by a wavelet tree. Pick a range <b>[l, r]</b> and a rank <b>k</b>, then press <b>Find k-th Smallest</b> to see the algorithm descend the tree level by level.</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">Find k-th Smallest</button>
  <button id="btnReset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Wavelet tree over a small sequence of integers.
// Supports k-th smallest in range [l,r] in O(log sigma) steps.
// Each node stores a bitvector: 0 = symbol goes to lo child, 1 = hi child.
// To find the k-th smallest in [l,r]:
//   1. Count zeros in [l,r] of the current node's bitvector => lo_count.
//   2. If k <= lo_count, recurse into lo child with the mapped range and k.
//   3. Otherwise recurse into hi child with the mapped range and k - lo_count.
//   4. At a leaf (range of size 1), the answer is that single symbol.

const SEQ = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 2];
const N = SEQ.length; // 16

// Build wavelet tree as array of levels.
// Each level is an array of 0/1 bits (same length as SEQ).
// Parallel: also track the alphabet range [lo, hi] at each level.
// We split [lo, hi] into [lo, mid] and [mid+1, hi].
// The level bitvector: 0 if seq[i] <= mid, else 1.
// After splitting, the order of elements within each half is preserved.

function buildLevels(seq, lo, hi) {
  if (lo >= hi) return [];
  const mid = Math.floor((lo + hi) / 2);
  const bits = seq.map(v => v <= mid ? 0 : 1);
  const loSeq = seq.filter(v => v <= mid);
  const hiSeq = seq.filter(v => v > mid);
  return [{ bits, lo, hi, mid }].concat(
    buildLevels(loSeq, lo, mid),
    buildLevels(hiSeq, mid + 1, hi)
  );
}

// Build a proper tree structure for navigation.
// node = { lo, hi, mid, bits, left, right }
function buildTree(seq, lo, hi) {
  if (lo >= hi) return { lo, hi, leaf: true, value: lo };
  const mid = Math.floor((lo + hi) / 2);
  const bits = seq.map(v => v <= mid ? 0 : 1);
  const loSeq = seq.filter(v => v <= mid);
  const hiSeq = seq.filter(v => v > mid);
  return {
    lo, hi, mid, bits, seq,
    left:  buildTree(loSeq, lo, mid),
    right: buildTree(hiSeq, mid + 1, hi),
    leaf: false
  };
}

const ROOT = buildTree(SEQ, 1, 9);

// Count zeros in bits[l..r] (0-indexed, inclusive)
function countZeros(bits, l, r) {
  let c = 0;
  for (let i = l; i <= r; i++) if (bits[i] === 0) c++;
  return c;
}
// Map position l (0-indexed) in parent seq to child (lo or hi) index.
// lo child: rank of zeros up to l-1 (number of 0s before position l)
function mapToLo(bits, pos) {
  let c = 0;
  for (let i = 0; i < pos; i++) if (bits[i] === 0) c++;
  return c;
}
function mapToHi(bits, pos) {
  let c = 0;
  for (let i = 0; i < pos; i++) if (bits[i] === 1) c++;
  return c;
}

// k-th smallest (1-indexed k) in node.seq[l..r] (0-indexed, inclusive)
// Returns { value, steps } where steps is array of { node, l, r, k, dir }
function kthSmallest(node, l, r, k) {
  const steps = [];
  function go(nd, l, r, k) {
    if (nd.leaf) {
      steps.push({ node: nd, l, r, k, dir: 'leaf' });
      return nd.value;
    }
    const zeros = countZeros(nd.bits, l, r);
    const dir = k <= zeros ? 'lo' : 'hi';
    steps.push({ node: nd, l, r, k, zeros, dir });
    if (dir === 'lo') {
      const nl = mapToLo(nd.bits, l);
      const nr = nl + zeros - 1;
      return go(nd.left, nl, nr, k);
    } else {
      const ones_before_l = mapToHi(nd.bits, l);
      const nl = ones_before_l;
      const nr = nl + (r - l + 1 - zeros) - 1;
      return go(nd.right, nl, nr, k - zeros);
    }
  }
  const value = go(node, l, r, k);
  return { value, steps };
}

// Render the original sequence with range highlighted
function renderSeq(l, r) {
  const row = document.getElementById('seqRow');
  row.innerHTML = '';
  SEQ.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'seq-cell' + (i >= l && i <= r ? ' in-range' : '');
    d.textContent = v;
    row.appendChild(d);
  });
}

// Render tree levels with bits highlighted for active range
function renderTree(steps) {
  const area = document.getElementById('treeArea');
  area.innerHTML = '';
  if (!steps || steps.length === 0) return;

  steps.forEach((step, si) => {
    const nd = step.node;
    if (nd.leaf) {
      const lbl = document.createElement('div');
      lbl.className = 'level-label';
      lbl.textContent = fmt('Step %si%%v%: leaf → answer = %value%', { si: si, v: 1, value: nd.value });
      area.appendChild(lbl);
      return;
    }
    const lbl = document.createElement('div');
    lbl.className = 'level-label';
    const info = step.dir === 'lo'
      ? fmt('zeros in [%l%,%r%] = %zeros% ≥ k=%k% → go LEFT (≤%mid%)', { l: step.l, r: step.r, zeros: step.zeros, k: step.k, mid: nd.mid })
      : fmt('zeros in [%l%,%r%] = %zeros% < k=%k% → go RIGHT (>%mid%)', { l: step.l, r: step.r, zeros: step.zeros, k: step.k, mid: nd.mid });
    lbl.textContent = fmt('Step %si%%v% [%lo%..%hi%]: %info%', { si: si, v: 1, lo: nd.lo, hi: nd.hi, info: info });
    area.appendChild(lbl);

    const row = document.createElement('div');
    row.className = 'level-row';
    nd.bits.forEach((b, i) => {
      if (i > 0 && i === step.l) {
        const sep = document.createElement('div'); sep.className = 'sep'; row.appendChild(sep);
      }
      const d = document.createElement('div');
      const inRange = i >= step.l && i <= step.r;
      d.className = 'bit-cell ' + (b === 0 ? 'lo' : 'hi') + (inRange ? ' active' : '');
      d.textContent = b;
      row.appendChild(d);
      if (i === step.r && step.r < nd.bits.length - 1) {
        const sep = document.createElement('div'); sep.className = 'sep'; row.appendChild(sep);
      }
    });
    area.appendChild(row);
  });
}

function run() {
  const l0 = parseInt(document.getElementById('inL').value, 10) - 1; // 0-indexed
  const r0 = parseInt(document.getElementById('inR').value, 10) - 1;
  const k  = parseInt(document.getElementById('inK').value, 10);
  const res = document.getElementById('result');

  if (isNaN(l0) || isNaN(r0) || isNaN(k) || l0 < 0 || r0 >= N || l0 > r0 || k < 1 || k > r0 - l0 + 1) {
    res.textContent = '⚠ Invalid input. Check that 1 ≤ l ≤ r ≤ 16 and 1 ≤ k ≤ (r−l+1).';
    res.className = 'result err';
    renderSeq(-1, -1); renderTree(null);
    return;
  }
  renderSeq(l0, r0);
  const { value, steps } = kthSmallest(ROOT, l0, r0, k);
  renderTree(steps);
  res.textContent = fmt('The %k%-th smallest value in positions [%l0%%v%, %r0%%v%] is %value%.', { k: k, l0: l0, v: 1, r0: r0, value: value });
  res.className = 'result ok';
  console.log('k-th smallest answer:', value, '| steps:', steps.length);
}

function reset() {
  document.getElementById('inL').value = 2;
  document.getElementById('inR').value = 10;
  document.getElementById('inK').value = 3;
  document.getElementById('treeArea').innerHTML = '';
  document.getElementById('result').textContent = '';
  document.getElementById('result').className = 'result';
  renderSeq(-1, -1);
}

document.getElementById('btnFind').addEventListener('click', run);
document.getElementById('btnReset').addEventListener('click', reset);
renderSeq(-1, -1);

Result

Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/wavelet-trees/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Wavelet Trees

One recursive split to rule rank, select and range