wavelettree

Wavelettree is a data structure used to represent a sequence over a finite alphabet in a compact form while supporting efficient queries. The term is commonly used in literature to refer to the wavelet tree, and some texts spell it as wavelettree. The wavelet tree enables operations such as access, rank, and select on the sequence, as well as various range queries.

Construction and design: The wavelet tree is a balanced rooted tree. The root corresponds to the whole alphabet. The alphabet is recursively partitioned into two halves; each node stores a bitvector indicating, for the positions in the subsequence, whether the symbol belongs to the left or right child. The process repeats down to leaves representing single symbols. The sequence is thus encoded across O(log sigma) levels, where sigma is the alphabet size.

Operations: Access(i) returns the symbol at position i by following the path from root to leaf, guiding decisions at each level using the node’s bitvectors. Rank(a, i) counts occurrences of a in the prefix [1..i], by traversing to the appropriate child at each level. Select(a, k) locates the position of the k-th occurrence of a. Range_count(l, r, a) and range_count(l, r, [a..b]) answer how many occurrences of a or a symbol range occur in a given interval, in O(log sigma) time. Additional queries include kth-order statistic in a range and quantile queries.

Space and complexity: Memory usage is roughly n log2(sigma) bits plus overhead for the bitvectors. Time for queries is O(log sigma). Applications include compressed text indexing, genomic data processing, and any scenario requiring fast substring-frequency queries on large alphabets.

See also: Wavelet matrix, succinct data structures.