competitive/data_structure/
disjoint_sparse_table.rs

1use super::SemiGroup;
2use std::{
3    fmt::{self, Debug, Formatter},
4    ops::Index,
5};
6
7pub struct DisjointSparseTable<S>
8where
9    S: SemiGroup,
10{
11    table: Vec<Vec<S::T>>,
12}
13
14impl<S> Clone for DisjointSparseTable<S>
15where
16    S: SemiGroup,
17{
18    fn clone(&self) -> Self {
19        Self {
20            table: self.table.clone(),
21        }
22    }
23}
24
25impl<S> Debug for DisjointSparseTable<S>
26where
27    S: SemiGroup,
28    S::T: Debug,
29{
30    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
31        f.debug_struct("DisjointSparseTable")
32            .field("table", &self.table)
33            .finish()
34    }
35}
36
37impl<S> DisjointSparseTable<S>
38where
39    S: SemiGroup,
40{
41    pub fn new(v: Vec<S::T>) -> Self {
42        let n = v.len();
43        let mut table = vec![v];
44        let mut k = 2;
45        while k < n {
46            let mut v = table[0].clone();
47            for i in (0..n).step_by(k * 2) {
48                for j in (i..n.min(i + k) - 1).rev() {
49                    v[j] = S::operate(&v[j], &v[j + 1]);
50                }
51                for j in i + k + 1..n.min(i + k * 2) {
52                    v[j] = S::operate(&v[j - 1], &v[j]);
53                }
54            }
55            table.push(v);
56            k *= 2;
57        }
58        Self { table }
59    }
60    #[inline]
61    pub fn height(&self) -> usize {
62        self.table[0].len()
63    }
64    #[inline]
65    fn most_significant_bit_place(x: usize) -> Option<usize> {
66        const C: u32 = usize::MAX.count_ones();
67        ((C - x.leading_zeros()) as usize).checked_sub(1)
68    }
69    #[inline]
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    }
80    #[inline]
81    pub fn fold(&self, l: usize, r: usize) -> S::T {
82        debug_assert!(l < r);
83        self.fold_close(l, r - 1)
84    }
85}
86
87impl<S> Index<usize> for DisjointSparseTable<S>
88where
89    S: SemiGroup,
90{
91    type Output = S::T;
92    #[inline]
93    fn index(&self, index: usize) -> &Self::Output {
94        &self.table[0][index]
95    }
96}
competitive/data_structure/disjoint_sparse_table.rs

competitive/data_structure/
disjoint_sparse_table.rs
