 Wavelet tree

A wavelet tree stores a sequence over an ordered alphabet by repeatedly splitting the alphabet into two parts. At an internal node, a bit vector records zero or one according to each element's part; the children receive the corresponding stable subsequences. The original wavelet-tree construction uses such relative position encodings to support compact indexed access.^[ref]

To answer a rank query for character $c$ in the first $r$ positions, follow the branch containing $c$. Replace $r$ by the number of that branch's bits among the current bit vector's first $r$ positions. At the leaf, the resulting $r$ is the answer. Stable filtering proves the invariant: it is the number of original-prefix elements reaching the current node.

For example, split $\{a,b,c,d\}$ as $\{a,b\}$ and $\{c,d\}$. The string cadaba gives root bit vector 101000 and left subsequence aaba. In its first five characters there are three left-part elements. The left bit vector 0010 contains two zeros among those first three positions, so the number of a occurrences is two. With constant-time bit rank queries and a balanced alphabet split, character rank queries take $O(\log |\Sigma |)$ time.