数列 - 一次元累積和 (Cumulative sum)

概要

一次元配列 \(x\) が与えられたとき, 任意の添字区間 \([l, r)\) に対して \[\sum_{i = l}^{r-1} x_i\] を \(O(1)\) で計算する.

数列中の値の変更は出来ないので注意.

メモ

値を動的に変更したい場合は BIT (Fenwick Tree) を使うと便利.

/// Sequence - Cumulative Summation 1D of Additive Group (+, 0)
use crate::algebra::group_additive::*;

#[derive(Debug)]
pub struct Cumsum1d<T>(Vec<T>);
impl<T: Copy + AGroup> Cumsum1d<T> {
    pub fn new(xs: &Vec<T>) -> Self {
        let mut ac = T::zero();
        let mut arr = vec![T::zero(); xs.len()];
        for i in 0..arr.len() {
            ac = ac + xs[i];
            arr[i] = ac;
        }
        Self(arr)
    }
    /// sum of [0, idx)
    fn sum_up(&self, idx: usize) -> T {
        if idx > 0 {
            self.0[idx - 1]
        } else {
            T::zero()
        }
    }
    /// sum(i..j) = sum of [i, j)
    pub fn sum(&self, range: std::ops::Range<usize>) -> T {
        if range.start >= range.end {
            T::zero()
        } else {
            self.sum_up(range.end) - self.sum_up(range.start)
        }
    }
}

#[cfg(test)]
mod test_cumsum {
    use crate::sequence::cumsum1d::*;

    fn naiiv(range: std::ops::Range<usize>, xs: &Vec<i64>) -> i64 {
        range.map(|i| xs[i]).sum()
    }

    fn autocheck(xs: Vec<i64>) {
        let n = xs.len();
        let cs = Cumsum1d::new(&xs);
        for left in 0..n {
            for right in 0..n {
                assert_eq!(cs.sum(left..right), naiiv(left..right, &xs));
            }
        }
    }

    #[test]
    fn test() {
        autocheck(vec![1, 3, 5, 2, 4, 6]);
        autocheck(vec![-1, -2, 0, -3]);
    }
}