= 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.<High-Order Entropy-Compressed Text Indexes by Roberto Grossi and others>[section 4.2, The Wavelet Tree]{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.
Back to article page
