dsalgo/
sparse_table_with_static_idempotent_binary_operation.rs

1pub trait BinaryOp {
2    type T;
3
4    fn f(
5        _: Self::T,
6        _: Self::T,
7    ) -> Self::T;
8}
9
10pub struct SparseTable<F: BinaryOp>(Vec<Vec<F::T>>);
11
12impl<F: BinaryOp> SparseTable<F>
13where
14    F::T: Clone,
15{
16    pub fn new(a: &[F::T]) -> Self {
17        let n = a.len();
18
19        assert!(n > 0);
20
21        let h = n.next_power_of_two().trailing_zeros().max(1) as usize;
22
23        let mut data = vec![vec![]; h];
24
25        data[0] = a.to_vec();
26
27        for i in 1..h {
28            let d1 = 1 << i;
29
30            let d0 = d1 >> 1;
31
32            let w = n - d1 + 1;
33
34            data[i] = (0..w)
35                .map(|j| {
36                    F::f(data[i - 1][j].clone(), data[i - 1][j + d0].clone())
37                })
38                .collect();
39        }
40
41        Self(data)
42    }
43
44    pub fn size(&self) -> usize {
45        self.0[0].len()
46    }
47
48    pub fn get(
49        &self,
50        l: usize,
51        r: usize,
52    ) -> F::T {
53        assert!(l < r && r <= self.size());
54
55        if r - l == 1 {
56            return self.0[0][l].clone();
57        }
58
59        let i = (r - l).next_power_of_two().trailing_zeros() as usize - 1;
60
61        F::f(self.0[i][l].clone(), self.0[i][r - (1 << i)].clone())
62    }
63}
64
65#[cfg(test)]
66
67mod tests {
68
69    use super::*;
70
71    #[test]
72
73    fn test() {
74        struct F;
75
76        impl BinaryOp for F {
77            type T = usize;
78
79            fn f(
80                x: usize,
81                y: usize,
82            ) -> usize {
83                x.min(y)
84            }
85        }
86
87        let a: Vec<usize> = vec![0, 4, 2, 8, 5, 1];
88
89        let sp = SparseTable::<F>::new(&a);
90
91        assert_eq!(sp.get(0, 4), 0);
92
93        assert_eq!(sp.get(3, 4), 8);
94
95        assert_eq!(sp.get(1, 6), 1);
96    }
97}
dsalgo/sparse_table_with_static_idempotent_binary_operation.rs

dsalgo/
sparse_table_with_static_idempotent_binary_operation.rs
