Prefix Sums

A prefix sum array (and its dual, the difference array) precomputes cumulative sums in $O(n)$ time so that the sum of any contiguous range [left..right] (or 2D sub-rectangle) can be answered in $O(1)$ constant time.

1D Prefix Sum with Leading Zero (`prefix.len() == arr.len() + 1`):
  Index:      0    1    2    3    4    5
  `arr`:         [ 10 | 20 |  5 | 30 | 15 ]
  `prefix`: [  0 | 10 | 30 | 35 | 65 | 80 ]
  Range Sum `arr[1..4]` (20 + 5 + 30)  ===  `prefix[4] - prefix[1]` (65 - 10 = 55) in O(1)!

Why Always Include a Leading 0 at prefix[0]

Building prefix of length n + 1 with prefix[0] = 0 and prefix[i + 1] = prefix[i] + arr[i] eliminates every if left == 0 boundary branch: the sum of the half-open slice arr[left..right] is unconditionally prefix[right] - prefix[left] for all 0 <= left <= right <= n!

1D Prefix Sum, 2D Prefix Sum, and Difference Arrays in Rust

/// 1D Prefix Sum supporting O(1) half-open range queries `[left..right]`.
pub struct PrefixSum1D {
    prefix: Vec<i64>,
}

impl PrefixSum1D {
    pub fn new(arr: &[i64]) -> Self {
        let mut prefix = Vec::with_capacity(arr.len() + 1);
        prefix.push(0);
        let mut acc = 0i64;
        for &x in arr {
            acc += x;
            prefix.push(acc);
        }
        Self { prefix }
    }

    /// Returns the sum of `arr[left..right]` in O(1) time.
    #[inline]
    pub fn query(&self, left: usize, right: usize) -> i64 {
        self.prefix[right] - self.prefix[left]
    }
}

/// 2D Prefix Sum supporting O(1) sub-rectangle queries `[r1..r2, c1..c2]`.
pub struct PrefixSum2D {
    cols: usize,
    pref: Vec<i64>,
}

impl PrefixSum2D {
    pub fn new(grid: &[Vec<i64>]) -> Self {
        let r_len = grid.len();
        let c_len = grid.first().map_or(0, Vec::len);
        let stride = c_len + 1;
        let mut pref = vec![0i64; (r_len + 1) * stride];

        for r in 0..r_len {
            for c in 0..c_len {
                pref[(r + 1) * stride + (c + 1)] = grid[r][c]
                    + pref[r * stride + (c + 1)]
                    + pref[(r + 1) * stride + c]
                    - pref[r * stride + c];
            }
        }
        Self { cols: stride, pref }
    }

    /// Returns the sum of sub-grid `rows [r1..r2)`, `cols [c1..c2)` in O(1) time!
    #[inline]
    pub fn query_rect(&self, r1: usize, c1: usize, r2: usize, c2: usize) -> i64 {
        let s = self.cols;
        self.pref[r2 * s + c2] - self.pref[r1 * s + c2] - self.pref[r2 * s + c1]
            + self.pref[r1 * s + c1]
    }
}

/// Applies `updates` of the form `(left, right_exclusive, delta)` in O(N + Q) total time
/// using a Difference Array.
pub fn apply_range_additions(len: usize, updates: &[(usize, usize, i64)]) -> Vec<i64> {
    let mut diff = vec![0i64; len + 1];
    for &(l, r, delta) in updates {
        diff[l] += delta;
        diff[r] -= delta;
    }

    let mut out = Vec::with_capacity(len);
    let mut running = 0i64;
    for &d in &diff[..len] {
        running += d;
        out.push(running);
    }
    out
}

fn main() {
    let p1 = PrefixSum1D::new(&[10, 20, 5, 30, 15]);
    assert_eq!(p1.query(1, 4), 55);

    let grid = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];
    let p2 = PrefixSum2D::new(&grid);
    // Sub-grid rows 1..3, cols 1..3 -> 5 + 6 + 8 + 9 = 28
    assert_eq!(p2.query_rect(1, 1, 3, 3), 28);

    let updated = apply_range_additions(5, &[(1, 4, 10), (2, 5, 5)]);
    assert_eq!(updated, vec![0, 10, 15, 15, 5]);

    println!("1D sum: {}, 2D rect sum: {}, Diff array: {updated:?}", p1.query(1, 4), p2.query_rect(1, 1, 3, 3));
}

1D sum: 55, 2D rect sum: 28, Diff array: [0, 10, 15, 15, 5]