前缀和数组 Prefix Sum Array

什么是前缀和数组? prefix_sum_array[i] = prefix_sum_array[i - 1] + arr[i],

上面的定义不好理解的话, 我们再看一下例子, 原数组是 arr[] = [1, 2, 3, 4, 5];, 则前缀和数组就是: prefix_sum = [1, 3, 6, 10, 15];.

前缀和数组的算法倒是蛮简单, 如下所示:

#![allow(unused)]
fn main() {
use std::ops::Add;

pub fn prefix_sum<T>(arr: &[T]) -> Vec<T>
where
    T: Clone + Add<T, Output=T>,
{
    if arr.is_empty() {
        return vec![];
    }
    let mut list = Vec::with_capacity(arr.len());
    list.push(arr[0].clone());
    for i in 1..arr.len() {
        list.push(arr[i].clone() + list[i - 1].clone());
    }
    debug_assert!(list.len() == arr.len());
    list
}
}

该算法的时间复杂度是 O(n), 空间复杂度是 O(n).

这种算法思想主要是用于缓存某些需要频繁计算的过程, 以空间换取时间.

前缀和数组的应用

给定一个数组 arr, 计算 arr[l] 与 arr[r] 之间的所有元素之和.

如果要频繁的计算部分数组之和的话, 每次计算都要从头算. 我们可以将前缀和数组缓存下来, 这样每次计算时 可以立即得到结果.

因为有下面的公式:

arr[left..=right].sum() = prefix_sum_array[right] - prefix_sum_array[left];

算法实现如下:

fn prefix_sum(numbers: &[i32]) -> Vec<i32> {
    let mut accum = 0;
    let mut ps = Vec::with_capacity(numbers.len());
    for num in numbers {
        accum += num;
        ps.push(accum);
    }
    ps
}

fn main() {
    let arr = [8, 19, 28, 21, 33, 97, 62, 7, 45];
    let ps = prefix_sum(&arr);
    for left in 0..2 {
        for right in 3..arr.len() {
            let sum = if left == 0 {
                ps[right]
            } else {
                ps[right] - ps[left - 1]
            };
            let sum_slice = arr[left..=right].iter().sum();
            assert_eq!(sum, sum_slice);
        }
    }
}