前缀和是指数组某个索引之前的所有元素的和，是一种重要的预处理手段，使用前缀和可以快速求出数组某一个区间的和。
示例：数组 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];
}
三、适用场景
前缀和数组适用于频繁计算静态数组的闭区间内的元素累加和。
练习题目：