【进阶算法】一维数组的前缀和

前缀和是指数组某个索引之前的所有元素的和，是一种重要的预处理手段，使用前缀和可以快速求出数组某一个区间的和。

示例：数组 arr = [8，1，3，-2，5，0，-3，6]，输入 m 个询问，每个询问输入一对l, r。对于每个询问，要求输出原数组中从第l个数到第r个数的和。

比如，第 1 次询问，输入 [0, 2]，需要输出 12；第 2 次询问，输入 [2, 5]，需要输出 6；第 3 次询问，输入 [0, 6]，需要输出 12。

这个问题可以很容易的通过遍历数组解决，但是每次都需要遍历数组，时间复杂度比较高。如果使用前缀和数组，可以大大提高运算效率。

一、前缀和数组

创建一个前缀和数组 preSum，保存原数组 arr 每个元素的前缀和，其中 preSum[0] = 0，preSum[i + 1] = arr[i] 的前缀和，也就是前缀和数组与原数组相比，下标向右偏移一位。这样，区间 [L, R] 的和就等于 preSum[R +1] - preSum[L]。原理如下：

preSum[R + 1] = arr[0] + arr[1] + arr[2] + ... + arr[L - 1] + arr[L] + arr[L + 1] + ... + arr[R - 1] + arr[R]
preSum[L] = arr[0] + arr[1] + arr[2] + ... + arr[L - 1] 
preSum[R + 1] - preSum[L] = arr[L] + arr[L + 1] + ... + arr[R - 1] + arr[R]

二、代码实现

// 原数组
int[] arr = {8, 1, 3, -2, 5, 0, -3, 6};
// 前缀和数组
int[] preSum = preSum(arr);

/**
 * 构造前缀和数组
 *
 * @param arr 原数组
 * @return 前缀和数组
 */
private int[] preSum(int[] arr) {
    int len = arr.length;
    int[] preSum = new int[len + 1];
    for (int i = 1; i <= len; i++) {
        preSum[i] = preSum[i - 1] + arr[i - 1];
    }
    return preSum;
}

/**
 * 获取数组闭区间 [left, right] 的累加和
 *
 * @param left  区间左边界
 * @param right 区间右边界
 * @return 数组闭区间 [left, right] 的累加和
 */
public int sumRange(int left, int right) {
    return preSum[right + 1] - preSum[left];
}

三、适用场景

前缀和数组适用于频繁计算静态数组的闭区间内的元素累加和。

练习题目：

LeetCode 303. 区域和检索 - 数组不可变