Struct WaveletTree 

pub struct WaveletTree { /* private fields */ }

Wavelet tree for range queries on integer sequences.

Supports range frequency, range nth-smallest, and range quantile all in O(log σ) time where σ is the alphabet size.

Implementations

impl WaveletTree

pub fn new(data: &[u64], lo: u64, hi: u64) -> Self

Construct a wavelet tree from a sequence of values in [lo, hi).

pub fn range_freq(&self, data: &[u64], l: usize, r: usize, v: u64) -> usize

Count occurrences of value v in range [l, r].

pub fn len(&self) -> usize

Return the sequence length.

pub fn is_empty(&self) -> bool

Return whether the wavelet tree is empty.

pub fn num_levels(&self) -> usize

Number of levels in the tree.