前缀和算法第一弹（一维前缀和和二维前缀和）

前言

1. 一维前缀和

（1）题目及示例

编辑

（2）暴力解法

（3）算法优化

2. 二维前缀和

（1）题目及示例

（2）暴力解法

（3）算法优化

前言

本文将从解决几道线上OJ题目，带你了解前缀和算法。从暴力解法讲起，进一步优化成最佳解法。

1. 一维前缀和

（1）题目及示例

题目链接：【模板】前缀和_牛客题霸_牛客网

如下图所示，第一行输入两个整数n和q，分别是3和2。其中n等于3，表示该数组中有三个数，第二行也会输入三个整数。q等于2，表示有两个查询，向第三行和第四行输入两个数字。

我们以第一次查询为例，输入为1和2，表示从数组第一个数加到第二个数，就是1加2等于3.

（2）暴力解法

对于这道题目，我们使用最直接的办法就是在一次查询中，输入两个数字x和y，直接从数组第x个元素开始一直加到第样个元素。

分析一下时间复杂度，假设数组元素个数是n，每次都要遍历完整个数组，也就是遍历n次，还有q次查询，那么时间复杂度就是O(n*q)。

代码如下，需要注意的是n的上限是10^5，而每个元素最大值是10^9，那么前缀和最大值是10^14，已经大于普通四字节整数的大小，需要使用long long64位整数。

#include <iostream>
#include <vector>
using namespace std;int main() {int n, q;while (cin >> n >> q) {vector<int> nums(n);for (int i = 0; i < n; i++) cin >> nums[i];while (q--) {int l, r;cin >> l >> r;long long ret = 0;for(int i = l-1; i < r; i++)ret += nums[i];// 打印区间和cout << ret << endl;}}return 0;
}

（3）算法优化

如果使用暴力解法，时间复杂度是O(n*q)，效率一般。我们可以使用前缀和来优化效率。

前缀和是快速求出数组中某一个连续区间的和。

如下图所示，arr数组里面有8个元素。我们创建一个dp数组，内部9个元素全为0。dp数组大小比arr数组多一个，这是因为数组的下标其实从0开始，而下面的index索引是从1开始，方便构建前缀和数组。
dp数组中第i个下标元素，表示arr数组index索引从1到i元素之和。因此，dp数组中第i个下标元素等于前一个元素加上arr数组中index索引为i的元素，可以通过一个式子dp[i]=dp[i-1]+arr[i-1]，其中index索引比数组下标大1。

在一轮查询中，输入两个输L和R，表示第L个元素到第 R个元素之间的和。如下图，相当于R的前缀和减去L-1的前缀和，即dp[R]-dp[L-1]。

#include <iostream>
#include <vector>
using namespace std;int main() {int n, q;while (cin >> n >> q) {vector<int> arr(n);for (int i = 0; i < n; i++) cin >> arr[i];// 构建前缀和表vector<long long> dp(n + 1, 0); // 使用n+1个元素初始化为0for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + arr[i - 1];}while (q--) {int l, r;cin >> l >> r;// 输出区间和，注意l和r是1-based索引cout << dp[r] - dp[l - 1] << endl;}}return 0;
}

分析一下时间复杂度，一开始需要构建前缀和表，遍历整个数组，相当于n次遍历。之后，有q次查询，每次查询不需要遍历数组，时间复杂度相当于O(1)。因此，总的时间复杂度是O(n+q)。

2. 二维前缀和

（1）题目及示例

题目链接：【模板】二维前缀和_牛客题霸_牛客网

如下图所示，第一行先输入两个数字式n和m，n为3，m为4。表示一个三行四列的矩阵，也是一个二维数组。第一行中最后一个数是3，表示有三次查询输入。

我们以第二次查询，即第六行输入为例。图中右边是一个三行四列的矩阵，第六行输入前两个参数是x1和y1，表示矩阵中第一行第一列的参数。后两个参数是x2和y2，表示第三行第三列的参数。题目中要求这两个参数为对顶点，由此框出来的黑色矩阵中所有元素之和。

（2）暴力解法

如果使用最直接的解法，根据题目给出的查询参数x1，y1，x2和y2，以此确定矩阵中求和范围，直接遍历数组进行求和。

分析时间复杂度，假设是n行m列的矩阵，每次都要遍历完整个数组，那么一次查询时间复杂度是O(n*m)。如果有q次查询，那么总的时间复杂度是O(n*m*q)。

如果测试矩阵非常大，查询次数非常多，可能会超时。

（3）算法优化

针对矩阵，或者说二维数组，我们可以使用二维前缀和。前缀和是数组中某个连续区间的和。arr数组是题目给出的二维矩阵，dp数组存储的就是前缀和。如下图，dp二维数组中宏方块位置的前缀和，是arr二维数组红色斜线位置的区域。

所以在进行查询之前，我们需要构建二维数组的前缀和。

如下图，我们把任意一个元素的前缀和抽象成为一个黑色正方形，对黑色正方形内部所有元素求和，就是该位置的前缀和。假设这是第x行第y列元素的前缀和，可以把该正方形切割成四个区域。
A区域是第x-1行第y-1列元素的前缀和，但是B和C区域的元素和不好求。我们用A和B结合在一起，A和C结合在一起，分别是蓝色斜线的区域和红色斜线区域。
蓝色斜线区域是第x-1行第y列元素的前缀和，红色斜线区域是第x行第y-1列元素的前缀和。而D就是该元素。

构建完前缀和表后，我们需要使用前缀和表来快速求出题目给出连续区间的和。

假设题目给出的参数是x1，y1，x2和y2。即第x1行第y1列元素和第x2行第y2列元素。
如下图所示，红色D区域就是所求元素和区域。我们可以把该区间分为四个区域。构建前缀和表时，我们知道下面四个区域之和就是(x2,y2)元素的前缀和，即dp[x2][y2]。
A区域是(x1-1,y1-1)元素的前缀和，而B区域和C区域不能直接使用前缀和表示。我们可以使用A与这两个区域结合。
那么A和B区域就是(x1-1,y2)元素的前缀和，A和C区域就是(x2,y1-1)元素的前缀和。
使用dp[x2][y2]减去A+B区域和A+C区域时，记得多加一个A区域前缀和。

如下是代码部分，构建前缀和表时，通常会把行和列多加一个，方便使用。

#include <iostream>
#include <vector>using namespace std;int main() 
{// 1.读数据int n = 0, m = 0, q = 0;while(cin >> n >> m >> q){// 构建数组vector<vector<int>> nums(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++)cin >> nums[i][j];}// 2. 构造二维前缀和矩阵vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++)dp[i][j] = dp[i-1][j] + dp[i][j-1] + nums[i][j] - dp[i-1][j-1];}vector<int> ret;int x1 = 0, y1 = 0, x2 = 0, y2 = 0;while(q--){cin >> x1 >> y1 >> x2 >> y2;// 求D区域元素和cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1 - 1] + dp[x1-1][y1-1] << endl; }}
}

分析一下时间复杂度，构建二维前缀和表，需要遍历一边二维数组，时间复杂度是O(n*m)。查询一次，不需要遍历数组，时间复杂度是O(1)。如果有q次查询，那么总的时间复杂度是O(n*m+q)。

对于其他关于求某个连续区间和的题目，需要根据具体问题来构建适合的前缀和表或者后缀和表。

创作充满挑战，但若我的文章能为你带来一丝启发或帮助，那便是我最大的荣幸。如果你喜欢这篇文章，请不吝点赞、评论和分享，你的支持是我继续创作的最大动力！