一、一维前缀和

1、算法推导

前缀和，从名字上看，我们就大概能知道算法的作用。前缀，就是某位置之前的所有数，为该数的前缀，前缀和，就是对该位置前缀的元素进行求和。

前缀和的模板其实非常简单，它更像是一种思想。

前缀和思想可以快速地解决问题，看个例子：

假如给定一段序列，需要你求出 [ l , r ] [l, r] [l,r] 区间的和，该如何求？

   最简单的方式就是通过 for 循环遍历一遍，时间复杂度为 O ( N ) O(N) O(N)

   而 前缀和算法 ，能在 O ( 1 ) O(1) O(1) 的时间复杂度完成

接下来我们来看，前缀和算法是如何在 O ( 1 ) O(1) O(1) 的时间复杂度求出和的：

前缀和算法主要分为两步，预处理 和 查询 ：假设 a , S a, S a,S 分别为 原数组 和 前缀和数组。

预处理 ：

预处理就是求 前缀和数组 。对于前缀和数组 s s s ，其中元素满足 S [ i ] = a [ 1 ] + a [ 2 ] + a [ 3 ] . . . a [ i ] S[i] = a[1] + a[2] + a[3] ... a[i] S[i]=a[1]+a[2]+a[3]...a[i]

求前缀和时，下标从 1 1 1 开始。

大体过程如下：

for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + q[i];
    }

前缀和数组每项 s[i] 是它的前一项  s[i−1] 加上原数组  a[i] 。

因为前缀和数组的前一项 s[i−1] ，是 a a a 数组中前  i−1 中前 i−1 项的值嘛，所以求 s[i] 时只要加上  a[i] 就可以计算出来前 i i i 项的前缀和了。

查询：

查询就是求给定区间 [l,r] 的值。现在由于求出了前缀和数组，那么查询时只要一步S[r]−S[l−1] ，就可以求出结果。

下面讲一下原理：

S 是前缀和数组，那么 S 中每一个位置元素都是  a 数组的前缀和，由此可得：

通过这一步骤，它们相同的元素被 抵消 ，最终结果就是 区间 [ l , r ] [l, r] [l,r] 的值 。

所以，我们发现，前缀和多开了一个数组，以达到优化计算时间的效果，是典型的 以空间换时间 的算法。

2、代码实现

接下来做道前缀和例题练练手。

链接：795. 前缀和

描述：

输入一个长度为  n 的整数序列。

接下来再输入m 个询问，每个询问输入一对  l,r。

对于每个询问，输出原序列中从第  l 个数到第r 个数的和。

输入格式：

第一行包含两个整数 n 和  m 。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数l 和r ，表示一个询问的区间范围。

输出格式：

共 m 行，每行输出一个询问的结果。

数据范围：

 1≤l≤r≤n

   1≤n,m≤100000

  −1000≤数列中元素的值≤1000

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

思路 ：典型的前缀和例题，思路我们上面已经讲过一遍了，直接开始写代码：

二、二维前缀和

二维前缀和是一维前缀和的加强。

从前只能求一维序列的前缀和，现在能求二维，也就是矩阵的前缀和。

1、算法推导

接下来看 二维前缀和数组 是如何构造的：

假设给定二维矩阵 a和s ， s 为前缀和矩阵，这里我们设定一个前提：竖直方向我们统一称为长，横平的边我们统一称为宽，以便我们描述图形。

假如要求 点  (i,j) 的前缀和，那么对于图中，以i,j 为长和宽的矩阵就是 点  (i,j) 的前缀和。

观察上图，可以得到面积公式：

一整块矩形面积=紫色面积+绿色面积+蓝色面积+红色面积

但是，对于矩阵的面积，有些地方是无法单独计算的，比如绿色区域，只能算以  i−1 为长， j 为高的面积。

所以，我们实际计算时，真正的计算公式 为：

一整块矩形面积=以 i−1 为长以 j 为高的矩形面积+以 i 为长以 j−1 为高的矩形面积−紫色面积 + 红色面积

以图表示：

至于为什么要加 紫色区域 呢？这是因为在加绿色矩阵和蓝色矩阵的时候，加了两次 紫色区域 ，所以需要去掉重复的这一块。

而这里的每一个与长和宽有直接关联的区域其实就是这一块区域的 前缀和 ，在  s 矩阵中都可以表示出来，而 红色小方格的面积 则是a 矩阵当前位置的元素，所以我们可以得到 二维矩阵前缀和预处理公式 ：

s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]

那么我们构造过程的代码也就可以写出来了：

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

而对于二维前缀和，我们的题型通常是求 子矩阵的和 ，比如：

以我们平常的思维方式，就是 两层循环遍历一下 ，时间复杂度为 O ( N × M ) O(N \times M) O(N×M)。

但是如果我们使用 前缀和 呢？实际上只需要 O ( 1 ) O(1) O(1) 的时间复杂度，是非常快的，但是前提得有公式，所以我们得先把公式推导出来。

推导过程 ：

我们再进行严格的区域划分，画一张较为详细的图：

同样的这里设定前提：竖直方向的边统一称为长，横平方向的边统一称为宽，以便我们描述图形。

根据上图，我们可以得出公式：

蓝色面积=以x2为长，y2为宽的区域面积−黄色面积−绿色面积−紫色面积

但是这里的区域面积也是不好算一小块的，区域的面积的长和宽要从 (1,1) 出发，所以我们 真正的公式 为：

蓝色面积=以x2为长y2为宽的区域面积−以x1−1为长y2为宽的区域面积−以x2为长y1−1为宽的区域面积+紫色面积

加上 紫色面积 的原因是，我们减去了两块 紫色面积 ，需要补上一个。

同样的，这里每块区域的面积，实际上就是 前缀和 ，比如 紫色面积就是 a a a 矩阵中以 x 1 − 1 x1- 1 x1−1 为长， y 1 − 1 y1 - 1 y1−1 的区域面积，前缀和形式就直接为 s [ x 1 − 1 ] [ y 1 − 1 ] s[x1 -1][y1 - 1] s[x1−1][y1−1]。

所以这里写出我们的 查询公式 ：

蓝色面积=s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]

到这里，我们的前缀和的核心公式都已经推导出来了，在做题目是就很方便了，只需要：预处理 + 查询 。

2、代码实现

链接：796. 子矩阵的和

对于每个询问输出子矩阵中所有数的和。

输入格式：

第一行包含三个整数  n，  m，  q 。

接下来 n 行，每行包含  m 个整数，表示整数矩阵。

接下来  q 行，每行包含四个整数 x1,y1,x2,y2 ，表示一组询问。

输出格式:

共    q 行，每行输出一个询问的结果。

数据范围:

1≤n,m≤1000

1≤q≤200000

1≤x1≤x2≤n

1≤y1≤y2≤m

−1000≤矩阵内元素的值≤1000

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

思路：

上面公式我们推导过了，直接预处理 + 查询即可：