haar_lib/ds/
sparse_table.rs

1//! 冪等性と結合性をもつ列の区間取得($O(1)$)ができる。
2
3use crate::algebra::traits::*;
4use crate::misc::range::range_bounds_to_range;
5use std::{cmp::min, ops::RangeBounds};
6
7/// 冪等性と結合性をもつ列の区間取得($O(1)$)ができる。
8pub struct SparseTable<A: Semilattice> {
9    semilattice: A,
10    data: Vec<Vec<A::Element>>,
11    log_table: Vec<usize>,
12    original_size: usize,
13}
14
15impl<A: Semilattice> SparseTable<A>
16where
17    A::Element: Clone + Default,
18{
19    /// **Time complexity** $O(n \log n)$
20    ///
21    /// **Space complexity** $O(n \log n)$
22    pub fn new(semilattice: A, s: Vec<A::Element>) -> Self {
23        let n = s.len();
24        let logn = n.next_power_of_two().trailing_zeros() as usize + 1;
25
26        let mut data = vec![vec![A::Element::default(); n]; logn];
27
28        data[0] = s;
29
30        for i in 1..logn {
31            for j in 0..n {
32                data[i][j] = semilattice.op(
33                    data[i - 1][j].clone(),
34                    data[i - 1][min(n - 1, j + (1 << (i - 1)))].clone(),
35                );
36            }
37        }
38
39        let mut log_table = vec![0; n + 1];
40        for i in 2..=n {
41            log_table[i] = log_table[i >> 1] + 1;
42        }
43
44        Self {
45            semilattice,
46            data,
47            log_table,
48            original_size: n,
49        }
50    }
51
52    /// **Time complexity** $O(1)$
53    pub fn fold(&self, range: impl RangeBounds<usize>) -> Option<A::Element> {
54        let (l, r) = range_bounds_to_range(range, 0, self.original_size);
55
56        if l >= r {
57            None
58        } else {
59            let k = self.log_table[r - l];
60            Some(
61                self.semilattice
62                    .op(self.data[k][l].clone(), self.data[k][r - (1 << k)].clone()),
63            )
64        }
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use std::fmt::Debug;
71
72    use crate::algebra::{
73        bit::{BitAnd, BitOr},
74        min_max::{Max, Min},
75    };
76
77    use super::*;
78    use rand::Rng;
79
80    fn test<A>(a: A, s: Vec<A::Element>)
81    where
82        A: Semilattice + Identity + Clone,
83        A::Element: Copy + Default + PartialEq + Debug,
84    {
85        let st = SparseTable::new(a.clone(), s.clone());
86
87        for l in 0..s.len() {
88            for r in l..=s.len() {
89                let ans = &s[l..r].iter().cloned().fold_m(&a);
90                assert_eq!(*ans, st.fold(l..r).unwrap_or(a.id()));
91            }
92        }
93    }
94
95    #[test]
96    fn test_max() {
97        let mut rng = rand::thread_rng();
98        let n = 100;
99        let s = std::iter::repeat_with(|| rng.gen::<u64>())
100            .take(n)
101            .collect::<Vec<_>>();
102        test(Max::<u64>::new(), s);
103    }
104
105    #[test]
106    fn test_min() {
107        let mut rng = rand::thread_rng();
108        let n = 100;
109        let s = std::iter::repeat_with(|| rng.gen::<u64>())
110            .take(n)
111            .collect::<Vec<_>>();
112        test(Min::<u64>::new(), s);
113    }
114
115    #[test]
116    fn test_bitand() {
117        let mut rng = rand::thread_rng();
118        let n = 100;
119        let s = std::iter::repeat_with(|| rng.gen::<u64>())
120            .take(n)
121            .collect::<Vec<_>>();
122        test(BitAnd::<u64>::new(), s);
123    }
124
125    #[test]
126    fn test_bitor() {
127        let mut rng = rand::thread_rng();
128        let n = 100;
129        let s = std::iter::repeat_with(|| rng.gen::<u64>())
130            .take(n)
131            .collect::<Vec<_>>();
132        test(BitOr::<u64>::new(), s);
133    }
134}
haar_lib/ds/sparse_table.rs

haar_lib/ds/
sparse_table.rs
