competitive_library/structure/
disjoint_sparse_table.rs

1use std::ops::Range;
2
3pub trait SemiGroup {
4    type T: Clone;
5    fn operate(a: &Self::T, b: &Self::T) -> Self::T;
6}
7
8pub struct Add {}
9impl SemiGroup for Add {
10    type T = i64;
11
12    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
13        *a + *b
14    }
15}
16
17#[derive(Debug)]
18pub struct DisjointSparseTable<S: SemiGroup> {
19    pub table: Vec<Vec<S::T>>,
20}
21
22impl<S: SemiGroup> DisjointSparseTable<S> {
23    #[inline]
24    pub fn new(v: &[S::T]) -> Self {
25        let size = (32 - (v.len() as u32).saturating_sub(1).leading_zeros()) as usize;
26        let mut table = vec![v.to_vec()];
27
28        (1..size).for_each(|i| {
29            let mut tmp = v.to_vec();
30
31            let span = 2i64.pow(i as u32) as usize;
32
33            (0..v.len().div_ceil(span * 2)).for_each(|j| {
34                let start = span * 2 * j + span;
35
36                (0..span - 1)
37                    .map(|k| start - 2 - k)
38                    .filter(|&k| k + 1 < v.len())
39                    .for_each(|k| {
40                        tmp[k] = S::operate(&tmp[k], &tmp[k + 1]);
41                    });
42
43                (0..span - 1)
44                    .map(|k| k + start + 1)
45                    .filter(|&k| k < v.len())
46                    .for_each(|k| {
47                        tmp[k] = S::operate(&tmp[k], &tmp[k - 1]);
48                    });
49            });
50            table.push(tmp);
51        });
52
53        DisjointSparseTable { table }
54    }
55
56    #[inline]
57    pub fn fold(&self, range: Range<usize>) -> S::T {
58        if range.len() == 1 {
59            return self.table[0][range.start].clone();
60        }
61        let h = (32 - ((range.start ^ (range.end - 1)) as u32).leading_zeros()) as usize - 1;
62        S::operate(&self.table[h][range.start], &self.table[h][range.end - 1])
63    }
64}
65
66#[cfg(test)]
67mod tests {
68
69    use super::*;
70
71    #[test]
72    fn test_disjoint_sparse_table() {
73        let a = DisjointSparseTable::<Add>::new(&[2, 10, 1, 100]);
74        for &(l, r, ans) in [
75            (0, 1, 2),
76            (0, 2, 12),
77            (0, 3, 13),
78            (0, 4, 113),
79            (1, 2, 10),
80            (1, 3, 11),
81            (1, 4, 111),
82            (2, 3, 1),
83            (2, 4, 101),
84            (3, 4, 100),
85        ]
86        .iter()
87        {
88            assert_eq!(a.fold(l..r), ans);
89        }
90    }
91
92    #[test]
93    fn test_library_checker_sample() {
94        let a = DisjointSparseTable::<Add>::new(&[1, 10, 100, 1000, 10000]);
95        for &(l, r, ans) in [
96            (2, 3, 100),
97            (0, 3, 111),
98            (2, 5, 11100),
99            (3, 4, 1000),
100            (0, 5, 11111),
101        ]
102        .iter()
103        {
104            assert_eq!(a.fold(l..r), ans);
105        }
106    }
107}
competitive_library/structure/disjoint_sparse_table.rs

competitive_library/structure/
disjoint_sparse_table.rs
