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

haar_lib/ds/
sparse_table.rs
