Struct WaveletMatrix

Source

pub struct WaveletMatrix { /* private fields */ }

Implementations§

Source §

impl WaveletMatrix

Source

pub fn new<T>(v: Vec<T>, bit_length: usize) -> Self
where T: Clone + RankSelectDictionaries,

Examples found in repository ?

crates/library_checker/src/datastructure/range_kth_smallest.rs (line 10)

6pub fn range_kth_smallest(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, a: [usize; n]);
10    let wm = WaveletMatrix::new(a, 30);
11    for (l, r, k) in scanner.iter::<(usize, usize, usize)>().take(q) {
12        writeln!(writer, "{}", wm.quantile(l..r, k)).ok();
13    }
14}

More examples

Hide additional examples

crates/competitive/src/data_structure/wavelet_matrix.rs (line 34)

29    pub fn new_with_init<T, F>(v: Vec<T>, bit_length: usize, mut f: F) -> Self
30    where
31        T: Clone + RankSelectDictionaries,
32        F: FnMut(usize, usize, T),
33    {
34        let this = Self::new(v.clone(), bit_length);
35        for (mut k, v) in v.into_iter().enumerate() {
36            for (d, &(c, ref b)) in this.table.iter().rev().enumerate().rev() {
37                if v.access(d) {
38                    k = c + b.rank1(k);
39                } else {
40                    k = b.rank0(k);
41                }
42                f(d, k, v.clone());
43            }
44        }
45        this
46    }

Source

pub fn new_with_init<T, F>(v: Vec<T>, bit_length: usize, f: F) -> Self
where T: Clone + RankSelectDictionaries, F: FnMut(usize, usize, T),

Source

pub fn access(&self, k: usize) -> usize

get k-th value

Source

pub fn rank(&self, val: usize, range: Range<usize>) -> usize

the number of val in range

Examples found in repository ?

crates/competitive/src/data_structure/wavelet_matrix.rs (line 75)

74    pub fn select(&self, val: usize, k: usize) -> Option<usize> {
75        if self.rank(val, 0..self.len) <= k {
76            return None;
77        }
78        let mut i = 0;
79        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
80            if val.access(d) {
81                i = c + b.rank1(i);
82            } else {
83                i = b.rank0(i);
84            }
85        }
86        i += k;
87        for &(c, ref b) in self.table.iter().rev() {
88            if i >= c {
89                i = b.select1(i - c).unwrap();
90            } else {
91                i = b.select0(i).unwrap();
92            }
93        }
94        Some(i)
95    }

Source

pub fn select(&self, val: usize, k: usize) -> Option<usize>

index of k-th val

Source

pub fn quantile(&self, range: Range<usize>, k: usize) -> usize

get k-th smallest value in range

Examples found in repository ?

crates/library_checker/src/datastructure/range_kth_smallest.rs (line 12)

6pub fn range_kth_smallest(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, a: [usize; n]);
10    let wm = WaveletMatrix::new(a, 30);
11    for (l, r, k) in scanner.iter::<(usize, usize, usize)>().take(q) {
12        writeln!(writer, "{}", wm.quantile(l..r, k)).ok();
13    }
14}

Source

pub fn quantile_outer(&self, range: Range<usize>, k: usize) -> usize

get k-th smallest value out of range

Source

pub fn rank_lessthan(&self, val: usize, range: Range<usize>) -> usize

the number of value less than val in range

Examples found in repository ?

crates/competitive/src/data_structure/wavelet_matrix.rs (line 153)

152    pub fn rank_range(&self, valrange: Range<usize>, range: Range<usize>) -> usize {
153        self.rank_lessthan(valrange.end, range.clone()) - self.rank_lessthan(valrange.start, range)
154    }