累積和 (Cumulative sum)

概要

\[\{ a_0, a_1,\ldots, a_n \} \mapsto \{ a_0, (a_0+a_1), \ldots, \sum_{i=0}^n a_n \}\]

seq.cumsum.rs

use std::ops::Range;
struct Cumsum { array: Vec<i32> }
impl Cumsum {
    fn new(xs: &Vec<i32>) -> Cumsum {
        let mut ac = 0;
        let mut arr = vec![0; xs.len()];
        for i in 0..arr.len() {
            ac += xs[i];
            arr[i] = ac;
        }
        Cumsum { array: arr }
    }
    fn sum_up(&self, idx: usize) -> i32 { // [0, idx)
        if idx > 0 {
            self.array[idx - 1]
        } else {
            0
        }
    }
    fn sum(&self, range: Range<usize>) -> i32 { // sum(i..j) = sum of [i, j)
        assert!(range.start <= range.end);
        self.sum_up(range.end) - self.sum_up(range.start)
    }
}
fn main() {
    {
        let xs = vec![1, 1, 2, 3];
        let cumsum = Cumsum::new(&xs);
        trace!(cumsum.array);
        assert!(cumsum.sum(0..1) == 1);
        assert!(cumsum.sum(0..2) == 2);
        assert!(cumsum.sum(0..3) == 4);
        assert!(cumsum.sum(0..4) == 7);
        assert!(cumsum.sum(2..4) == 5);
        assert!(cumsum.sum(1..1) == 0);
        assert!(cumsum.sum(2..2) == 0);
    }
}