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

haar_lib/ds/
cumulative_sum_1d.rs
