haar_lib/ds/
cumulative_sum_1d.rs

1//! 1次元累積和
2
3pub use crate::algebra::traits::Group;
4use std::ops::{Index, Range};
5
6/// 1次元の累積和を扱う
7#[derive(Debug, Clone)]
8pub struct CumulativeSum1D<G: Group> {
9    data: Vec<G>,
10}
11
12/// [`CumulativeSum1D`]を構築する
13pub struct CumulativeSum1DBuilder<G: Group> {
14    data: Vec<G>,
15}
16
17impl<G: Group + Copy> CumulativeSum1D<G> {
18    /// **Time complexity** $O(1)$
19    pub fn fold(&self, Range { start: l, end: r }: Range<usize>) -> G {
20        self.data[r].op(self.data[l].inv())
21    }
22}
23
24impl<G: Group> Index<usize> for CumulativeSum1D<G> {
25    type Output = G;
26
27    fn index(&self, i: usize) -> &Self::Output {
28        &self.data[i]
29    }
30}
31
32impl<G: Group + Copy> CumulativeSum1DBuilder<G> {
33    /// `CumulativeSum1DBuilder`を生成する
34    pub fn new(n: usize) -> Self {
35        CumulativeSum1DBuilder {
36            data: vec![G::id(); n + 1],
37        }
38    }
39
40    /// `i`番目に`value`を代入する
41    pub fn assign(&mut self, i: usize, value: G) {
42        self.data[i + 1] = value;
43    }
44
45    /// 群`G`の演算に`i`番目の値と`value`を適用して`i`番目の値を更新する。
46    pub fn update(&mut self, i: usize, value: G) {
47        self.data[i + 1] = self.data[i + 1].op(value);
48    }
49
50    /// [`CumulativeSum1D`]を構築する
51    pub fn build(self) -> CumulativeSum1D<G> {
52        let data = self
53            .data
54            .iter()
55            .scan(G::id(), |st, &x| {
56                *st = st.op(x);
57                Some(*st)
58            })
59            .collect::<Vec<_>>();
60
61        CumulativeSum1D { data }
62    }
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68    use crate::algebra::sum::*;
69    use my_testtools::*;
70    use rand::Rng;
71
72    #[test]
73    fn test() {
74        let mut rng = rand::thread_rng();
75
76        let n = 20;
77        let mut csb = CumulativeSum1DBuilder::<Sum<i32>>::new(n);
78
79        let mut other = vec![Sum::id(); n];
80
81        for _ in 0..1000 {
82            let i = rng.gen_range(0..n);
83            let x = rng.gen_range(-1000..=1000);
84
85            csb.update(i, Sum(x));
86            other[i].op_assign_r(Sum(x));
87        }
88
89        let cs = csb.build();
90
91        for _ in 0..100 {
92            let range = rand_range(&mut rng, 0..n);
93            let ans = other[range.clone()].iter().cloned().fold_m();
94            assert_eq!(cs.fold(range), ans);
95        }
96    }
97}
haar_lib/ds/cumulative_sum_1d.rs

haar_lib/ds/
cumulative_sum_1d.rs
