Wavelet Tree

A recursive structure over the value range rather than the index range. It answers rank, select, quantile and range-count queries in $O(\log C)$ using $O(n\log C)$ bits — succinct enough to fit datasets a segment tree could not.

The construction

Split the value range $[lo,hi]$ at its midpoint. Partition the sequence stably into elements $\le mid$ (left) and $>mid$ (right), and record for each position a bit saying which side it went to. Store a rank structure (prefix sums) over those bits, then recurse on each half.

values: 3 1 4 1 5 9 2 6      range [1,9], mid = 5
bits:   0 0 0 0 0 1 0 1
left:   3 1 4 1 5 2          range [1,5]
right:  9 6                  range [6,9]

Depth $O(\log C)$, one bit per element per level → $O(n\log C)$ bits.

The core primitive

rank(i) on a level’s bit vector = “how many of the first $i$ elements went left”. With prefix sums this is $O(1)$, and it lets you map an index range $[l,r)$ at one level to the corresponding range at either child:

• left child: $[\mathrm{rank}(l),\mathrm{rank}(r))$
• right child: $[l-\mathrm{rank}(l),r-\mathrm{rank}(r))$

Every query is a walk down the tree, remapping the range at each step.

What it answers

Query	Method	Cost
$k$-th smallest in $[l,r]$	descend: if $k\le$ (count going left), go left, else subtract and go right	$O(\log C)$
Count of elements $\le x$ in $[l,r]$	descend, accumulating whole left subtrees	$O(\log C)$
Count of elements in $[a,b]$ in $[l,r]$	difference of two counts	$O(\log C)$
rank: occurrences of $v$ in $[l,r]$	descend to $v$‘s leaf	$O(\log C)$
select: position of the $k$-th occurrence of $v$	descend to the leaf, then walk back up	$O(\log C)$
Sum of elements $\le x$ in $[l,r]$	store prefix sums per level as well	$O(\log C)$
Number of distinct values in $[l,r]$	✘ — needs a different structure

Comparison for “$k$-th smallest in a range”

Structure	Build	Query	Memory	Online	Updates
Sort the range	—	$O(n\log n)$	$O(1)$	✔	✔
Merge sort tree + binary search	$O(n\log n)$	$O({\log }^{3}n)$	$O(n\log n)$	✔	✘
Persistent segment tree	$O(n\log n)$	$O(\log n)$	$O(n\log n)$ ints	✔	✘
Wavelet tree	$O(n\log C)$	$O(\log C)$	$O(n\log C)$ bits	✔	✘
Mo’s + a value BIT	—	$O(\sqrt{n}\log n)$	$O(n)$	✘	✘
Offline BIT sweep	—	$O(\log n)$ am.	$O(n)$	✘	✔

The persistent segment tree is the more common contest choice — the code is shorter and most people already have a persistent segtree template. The wavelet tree’s advantage is memory: bits instead of integers, a 32-64× saving, which matters for very large $n$.

Where wavelet trees really live

They come from succinct data structures and text indexing:

• FM-index — a compressed full-text index built on the Burrows-Wheeler transform, with a wavelet tree providing the rank queries. This is what modern DNA aligners (BWA, Bowtie) use.
• Compressed suffix arrays.
• Document retrieval — “which documents contain this pattern”.
• Range median / quantile in large datasets, where memory is the binding constraint.

Updates

Not supported in the plain version — the bit vectors would need re-partitioning. A wavelet matrix (a flattened variant with better cache behaviour) has the same limitation. If you need updates, use an offline sweep or a sqrt decomposition over values.

See also: Persistent Structures · Merge Sort Tree · K-th Order Statistics