Struct DisjointSparseTable

Source

pub struct DisjointSparseTable<S>where
    S: SemiGroup,
{ /* private fields */ }

Implementations§

Source §

impl<S> DisjointSparseTable<S>
where S: SemiGroup,

Source

pub fn new(v: Vec<S::T>) -> Self

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 143)

141    pub fn gen_lca<D: LcaMonoidDispatch>(&'a self) -> LowestCommonAncestor<'a, D> {
142        D::set_depth(self.graph.tree_depth(self.root));
143        let dst = DisjointSparseTable::<LcaMonoid<D>>::new(self.vtrace.clone());
144        LowestCommonAncestor { euler: self, dst }
145    }

More examples

Hide additional examples

crates/library_checker/src/datastructure/staticrmq.rs (line 13)

9pub fn staticrmq_disjoint_sparse_table(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
13    let table = DisjointSparseTable::<MinOperation<_>>::new(a);
14    for (l, r) in lr.take(q) {
15        writeln!(writer, "{}", table.fold(l, r)).ok();
16    }
17}

Source

pub fn height(&self) -> usize

Examples found in repository ?

crates/competitive/src/data_structure/disjoint_sparse_table.rs (line 71)

70    pub fn fold_close(&self, l: usize, r: usize) -> S::T {
71        debug_assert!(l < self.height());
72        debug_assert!(r < self.height());
73        debug_assert!(l <= r);
74        if let Some(x) = Self::most_significant_bit_place(l ^ r) {
75            S::operate(&self.table[x][l], &self.table[x][r])
76        } else {
77            self.table[0][l].clone()
78        }
79    }

Source

pub fn fold_close(&self, l: usize, r: usize) -> S::T

Examples found in repository ?

crates/competitive/src/data_structure/disjoint_sparse_table.rs (line 83)

81    pub fn fold(&self, l: usize, r: usize) -> S::T {
82        debug_assert!(l < r);
83        self.fold_close(l, r - 1)
84    }

Source

pub fn fold(&self, l: usize, r: usize) -> S::T

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 165)

164    pub fn lca(&self, u: usize, v: usize) -> usize {
165        self.euler.query(u, v, |l, r| self.dst.fold(l, r))
166    }

More examples

Hide additional examples

crates/library_checker/src/datastructure/staticrmq.rs (line 15)

9pub fn staticrmq_disjoint_sparse_table(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
13    let table = DisjointSparseTable::<MinOperation<_>>::new(a);
14    for (l, r) in lr.take(q) {
15        writeln!(writer, "{}", table.fold(l, r)).ok();
16    }
17}