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<T: Debug>,
28{
29    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
30        f.debug_struct("DisjointSparseTable")
31            .field("table", &self.table)
32            .finish()
33    }
34}
35
36impl<S> DisjointSparseTable<S>
37where
38    S: SemiGroup,
39{
40    pub fn new(v: Vec<S::T>) -> Self {
41        let n = v.len();
42        let mut table = vec![v];
43        let mut k = 2;
44        while k < n {
45            let mut v = table[0].clone();
46            for i in (0..n).step_by(k * 2) {
47                for j in (i..n.min(i + k) - 1).rev() {
48                    v[j] = S::operate(&v[j], &v[j + 1]);
49                }
50                for j in i + k + 1..n.min(i + k * 2) {
51                    v[j] = S::operate(&v[j - 1], &v[j]);
52                }
53            }
54            table.push(v);
55            k *= 2;
56        }
57        Self { table }
58    }
59    #[inline]
60    pub fn height(&self) -> usize {
61        self.table[0].len()
62    }
63    #[inline]
64    fn most_significant_bit_place(x: usize) -> Option<usize> {
65        const C: u32 = usize::MAX.count_ones();
66        ((C - x.leading_zeros()) as usize).checked_sub(1)
67    }
68    #[inline]
69    pub fn fold_close(&self, l: usize, r: usize) -> S::T {
70        debug_assert!(l < self.height());
71        debug_assert!(r < self.height());
72        debug_assert!(l <= r);
73        if let Some(x) = Self::most_significant_bit_place(l ^ r) {
74            S::operate(&self.table[x][l], &self.table[x][r])
75        } else {
76            self.table[0][l].clone()
77        }
78    }
79    #[inline]
80    pub fn fold(&self, l: usize, r: usize) -> S::T {
81        debug_assert!(l < r);
82        self.fold_close(l, r - 1)
83    }
84}
85
86impl<S> Index<usize> for DisjointSparseTable<S>
87where
88    S: SemiGroup,
89{
90    type Output = S::T;
91    #[inline]
92    fn index(&self, index: usize) -> &Self::Output {
93        &self.table[0][index]
94    }
95}
competitive/data_structure/disjoint_sparse_table.rs

competitive/data_structure/
disjoint_sparse_table.rs
