Module qwt::quadwt

This module implements a Quad Wavelet Tree to support access, rank, and select queries on a vector of unsigned integers.

This data structure supports three operations:

• get(i) accesses the i-th symbols of the indexed sequence;
• rank(s, i) counts the number of occurrences of symbol s up to position i excluded;
• select(s, i) returns the position of the i-th occurrence of symbol s.

We can index vectors of length up to 2^{43} symbols.

Structs

• QWTIterator
• QWaveletTree
  The generic RS is the data structure we use to index a quaternary sequence to support access, rank, and select` queries.

Traits

• RSforWT
  Alias for the trait bounds to be satisfied by a data structure to support rank and select queries at each level of the wavelet tree. We need an alias to avoid repeating a lot of bounds here and there.
• WTIndexable
  Alias for the trait bounds of the type T to be indexable in the wavelet tree.