✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343 📣专栏定位：为 0 基础刚入门数据结构与算法的小伙伴提供详细的讲解，也欢迎大佬们一起交流~ 📚专栏地址：https://blog.csdn.net/Newin2020/article/details/126445229 ❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

在有些题目中，需要我们快速的获得一个区间值的和，如果每次查询都循环一个个加的话，时间复杂度会比较大，这时候就要用到前缀和算法，查询区间和的时候，时间复杂度只有 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

该题需要我们查询一段区间的和，我们看来看看如何用前缀和来做，首先来看看原理。

前缀和需要用到一个数组 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] 得到结果，如下图所示。

在有些题目中，需要我们求一片区域中元素值的和，这其实就是一维前缀和的扩展，来看一道模板题。

输入一个 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 的矩阵，如下图所示。

现在需要我们求一片区域中元素值的和，假定给定一个左上角坐标 (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] 就是重复的区域（上图绿色区域），要补上这多减的一次，从而得到最终结果。

恭喜您成功点亮前缀和算法技能点！

一维前缀和查询的时候，我们需要注意其边界，当查询区间 [l,r] 的和时，减去的是 sum[l-1] 而不是 sum[l]，因为 sum[l] 包含了 a[l]。

二维前缀和计算及查询的时候，我们需要注意其重复区域，计算时重复区域被加了 2 次，故要减去 1 次；而查询时重复区域被减了 2 次，故要加上 1 次。

另外，还要注意我们上面建立的坐标系和正常见到的坐标系不同，这里是倒过来的，即 x 轴往由延伸，y 轴往下延伸，这样方便我们进行计算。