前缀和（preSum）算法是一种数据预处理方法，可用于快速求数组的区间和。前缀和是一种典型的空间换时间思想的应用。
前缀和可以简单地理解为数组的前 i 个元素的和。

前缀和的应用

前缀和可以应用在：

  1. 快速求数组前i位之和；
  2. 快速求数组的 [i, j] 范围内之和；
  3. 求二维矩阵中某个子矩阵之和。

例题 1：「力扣」的 1480. 一维数组的动态和。

IMG20211118195841.png

常规做法 给定一个区间 [i,j] 我们遍历从 i 累加到 j 这样单词时间复杂度是 算法-【前缀和】 - 图2,如果查询n次检索，则需要算法-【前缀和】 - 图3 时间复杂度。即下面的代码这样使用两重循环。

  1. class Solution {
  2.     public int[] runningSum(int[] nums) {
  3.         int N = nums.length;
  4.         int[] preSum = new int[N];
  5.         for (int i = 0; i < N; ++i) {
  6.             int sum = 0;
  7.             for (int j = 0; j <= i; ++j) {
  8.                 sum += nums[j];
  9.             }
  10.             preSum[i] = sum;
  11.         }
  12.         return preSum;
  13.     }
  14. }

这样效率是比较低的。其实我们只要稍微转变一下思路，就发现没必要用两重循环。
当已知 preSum[i] 是数组前 i 项的和，那么数组的前i + 1项的和 preSum[i + 1] = preSum[i] + nums[i + 1]。一个简单的转换，让我们可以省去内层的 for 循环。
这也就是前缀和的核心思想。代码如下

  1. class Solution {
  2.     public int[] runningSum(int[] nums) {
  3.         int N = nums.length;
  4.         int[] preSum = new int[N + 1];
  5.         for (int i = 0; i < N; ++i) {
  6.             preSum[i + 1] = preSum[i] + nums[i];
  7.         }
  8.         return preSum;
  9.     }
  10. }

前缀和的思想比较简单，就是预处理数组对于每个位置i我们都求出他的前i-1项的和,这样我们后续就可以以算法-【前缀和】 - 图4 的时间复杂度来快速的求出前 N 项的和。还可以顺带求出某个区间[i,j]的和，
根据我们定义的preSum可知 preSum[j+1] 代表[0,1,2,3.....j]的元素和，preSum[i]代表[0,1,2,3,,,,,,i-1] 的和，不难发现两式相减可得 [i,i+1,i+2,,,,,,j]的和。

**Sum[i,j] = preSum[j+1] - preSum[i]**

采用前缀和本题就可以将时间复杂度降到算法-【前缀和】 - 图5

前缀和的扩展

有一种常见的是二维矩阵前缀和

例题 2. 「力扣」的 304. 二维区域和检索 - 矩阵不可变。

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为(row1, col1)，右下角 为(row2, col2)。 实现 NumMatrix类：

  • NumMatrix(int[][] matrix)给定整数矩阵 matrix进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2)返回 左上角(row1, col1)、右下角(row2, col2)所描述的子矩阵的元素 总和 。

IMG20211118202235.png

输入:
[“NumMatrix”,”sumRegion”,”sumRegion”,”sumRegion”]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

如果常规方法来做的话我们每次都需要遍历子矩阵求和需要时间复杂度为算法-【前缀和】 - 图7，执行n次检索总共时间复杂度 算法-【前缀和】 - 图8。
我们可以用前缀和来优化，次数定义 preSum[i][j] 表示 从 [0,0] 位置到 [i,j] 位置的子矩形所有元素之和。
preSum[i][j] 的递推公式为：
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i][j]preSum[i][j]=preSum[i−1][j]+preSum[i][j−1]−preSum[i−1][j−1]+matrix[i][j]

IMG20211118204146.png

借助上述图来理解。
此时算法-【前缀和】 - 图10
减去算法-【前缀和】 - 图11的原因是因为他被累加了两次。

有了这个我们就很容易先预处理矩阵得到任意的 从 [0,0] 位置到 [i,j] 位置的子矩形所有元素之和，然后再利用O(1)的时间求出每次检索需要的答案。

AC代码如下

  1. class NumMatrix {
  2.     int[][] preSum = null; 
  3.     public NumMatrix(int[][] matrix) {
  4.         int rlen = matrix.length;
  5.         if(rlen>0){
  6.              int clen = matrix[0].length;
  7.              preSum = new int [rlen+1][clen+1];
  8.              for(int i=0;i<rlen;i++){
  9.                 for(int j=0;j<clen;j++){
  10.                     preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] - preSum[i][j] + matrix[i][j]; 
  11.                 }
  12.              }
  13.         }
  15.     }
  17.     public int sumRegion(int row1, int col1, int row2, int col2) {
  18.        return preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1];
  19.     }
  20. }
  22. /**
  23.  * Your NumMatrix object will be instantiated and called as such:
  24.  * NumMatrix obj = new NumMatrix(matrix);
  25.  * int param_1 = obj.sumRegion(row1,col1,row2,col2);
  26.  */

注意事项

如果矩阵可修改，或者上述例题一的数组可以修改的话，那么我们就没办法利用该方式预处理数组了。因为某一项元素改变后此时会影响所有的范围区间和，这时我们需要用到另外一种数据结构来有效的来解决数组可变的问题。树状数组 或者 线段树 本文这里不做过多讲解。