前缀和
在有些题目中，需要我们快速的获得一个区间值的和，如果每次查询都循环一个个加的话，时间复杂度会比较大，这时候就要用到前缀和算法，查询区间和的时候，时间复杂度只有 O(1)，废话少说，直接上图解。
一维前缀和
首先，我们来看到一维前缀和的模板题，以题带图解的模式带大家深入理解。
输入一个长度为 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
该题需要我们查询一段区间的和，我们看来看看如何用前缀和来做，首先来看看原理。
前缀和需要用到一个数组 sum，其中 sum[i] 存储的是 a[1] 到 a[i] 元素值的和，这样只要将该数组计算出来，后续计算的时候就只需 O(1) 的时间复杂度。在代码实现时，我们可以用循环来计算前缀和，用上一轮的计算结果加到本轮当中：
s u m [ i ] = s u m [ i − 1 ] + a [ i ] = a [ 1 ] + . . . + a [ i ] sum[i]=sum[i-1]+a[i]=a[1]+...+a[i]sum[i]=sum[i−1]+a[i]=a[1]+...+a[i]
为了方便理解， 假设我们要查询 [3,6] 区间的和，按照上述原理给出对应 sum 中储存的值。
s u m [ 2 ] = a [ 1 ] + a [ 2 ] sum[2]=a[1]+a[2]sum[2]=a[1]+a[2]
s u m [ 3 ] = a [ 1 ] + a [ 2 ] + a [ 3 ] sum[3]=a[1]+a[2]+a[3]sum[3]=a[1]+a[2]+a[3]
s u m [ 6 ] = a [ 1 ] + a [ 2 ] + a [ 3 ] + a [ 4 ] + a [ 5 ] + a [ 6 ] sum[6]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]sum[6]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]
我们只需计算 sum[6]-sum[2] 的结果即可得到区间 [3,6] 的和，注意这里是减去 sum[2] 而不是 sum[3]，因为 sum[3] 包含了 a[3]，这在 [3,6] 区间当中。
a n s = s u m [ 6 ] − s u m [ 2 ] = ( a [ 1 ] + a [ 2 ] + a [ 3 ] + a [ 4 ] + a [ 5 ] + a [ 6 ] ) − ( a [ 1 ] + a [ 2 ] ) = a [ 3 ] + a [ 4 ] + a [ 5 ] + a [ 6 ] ans=sum[6]-sum[2]=(a[1]+a[2]+a[3]+a[4]+a[5]+a[6])-(a[1]+a[2])=a[3]+a[4]+a[5]+a[6]ans=sum[6]−sum[2]=(a[1]+a[2]+a[3]+a[4]+a[5]+a[6])−(a[1]+a[2])=a[3]+a[4]+a[5]+a[6]
因此，我们可以得到通用公式，查询区间 [l,r] 的和为：
a n s = s u m [ r ] − s u m [ l − 1 ] ans=sum[r]-sum[l-1]ans=sum[r]−sum[l−1]
实现的时候我们一般从下标 1 开始计算，防止数组越界的情况。
为了加深理解，我们拿题目样例进行模拟，给定一个数组 {2, 1, 3, 6, 4}，现在需要查询 [2,4] 区间的和。首先需要计算前缀和，然后通过公式 sum[4]-sum[2-1] 得到结果，如下图所示。
#include<bits/stdc++.h> using namespace std; int main() { int a[100000], sum[100000]; int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } //计算前缀和 for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + a[i]; } //进行查询 while (m--) { int l, r; scanf("%d %d", &l, &r); printf("%d\n", sum[r] - sum[l - 1]); } }
二维前缀和
在有些题目中，需要我们求一片区域中元素值的和，这其实就是一维前缀和的扩展，来看一道模板题。
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 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
这其实和一位前缀和十分相似，只不过多了一维，为了方便理解，这次我们先对题目样例进行模拟，题目给定了一个 3×4 的矩阵，如下图所示。
现在需要我们求一片区域中元素值的和，假定给定一个左上角坐标 (2,2)，一个右下角坐标 (3,3)，则查询的区间如下图所示（红色区域）。
注意，这里的下标是从 1 开始计算，并且原点在左上角，即 (2,2) 是第二行第二个值 6，而 (3,3) 是第三行第三个值 2。
可以看到，一维数组的前缀和无法查询出上述情况，这就要用到二维数组了，现在我们再来看看原理。
计算
定义一个二维前缀和数组 s，其中 s[i][j] 表示从左上角 (1,1) 开始到右下角 (i,j) 这一片矩形中元素值的和。这时，我们在计算前缀和的时候就不像一维一样简洁了，需要考虑到区间重复问题，我先给出二维前缀和的计算公式：
s [ i ] [ j ] = s [ i − 1 ] [ j ] + s [ i ] [ j − 1 ] − s [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]
不要着急，我们一步步来解析，假设现在求的是 s[3][3]，其运算公式如下：
s [ 3 ] [ 3 ] = s [ 2 ] [ 3 ] + s [ 3 ] [ 2 ] − s [ 2 ] [ 2 ] + a [ 3 ] [ 3 ] s[3][3]=s[2][3]+s[3][2]-s[2][2]+a[3][3]s[3][3]=s[2][3]+s[3][2]−s[2][2]+a[3][3]
其覆盖的范围如下图所示（红色区域）。
获得该区域的和需要用到之前计算出的两个区域和一个值 a[i][j]，而这两个区域分别是 s[i-1][j] 和 s[i][j-1] 即 s[2][3] 和 s[3][2]。
但如果将这两个区域的和加起来，可以发现出现了重复的区域（上图绿色区域）即该区域计算了两次。故在计算的时候，我们还需要减去一次重复区域即减去 s[i-1][j-1] 即 s[2][2] 就是最后的结果。
查询
再来看查询的情况，查询的计算公式其实和上面相反，运算的时候同样会遇到重复区域，只不过这里是多减了一个重复区域，需要运算的时候加上。假设左上角坐标为 (x1,y1)，右下角为 (x2,y2)，可以得到如下公式：
a n s = s [ x 2 ] [ y 2 ] − s [ x 1 − 1 ] [ y 2 ] − s [ x 2 ] [ y 1 − 1 ] + s [ x 1 − 1 ] [ y 1 − 1 ] ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]ans=s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]
我们来看开头举的那个例子，左上角坐标为 (2,2)，右下角坐标为 (3,3)，所以运算公式如下：
a n s = s [ 3 ] [ 3 ] − s [ 1 ] [ 3 ] − s [ 3 ] [ 1 ] + s [ 1 ] [ 1 ] ans=s[3][3]-s[1][3]-s[3][1]+s[1][1]ans=s[3][3]−s[1][3]−s[3][1]+s[1][1]
其中 s[1][1] 就是重复的区域（上图绿色区域），要补上这多减的一次，从而得到最终结果。
代码
#include<bits/stdc++.h> using namespace std; int n, m, q; int a[1005][1005]; int s[1005][1005]; int main() { scanf("%d%d%d", &n, &m, &q); //计算前缀和 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; } } //进行查询 while (q--) { int x1, x2, y1, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); } return 0; }
