初识算法 · 前缀和(1)
目录
前言：
一维数组的前缀和
题目解析
算法原理
算法编写
二维数组的前缀和
题目解析
算法原理
算法编写
前言：
本文的主题是前缀和，通过两道题目讲解，一道是一维数组的模板，一道是二维数组的模板。
链接分别为：
【模板】前缀和_牛客题霸_牛客网
【模板】二维前缀和_牛客题霸_牛客网
题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。
一维数组的前缀和
题目解析
题目看起来是较为复杂的，一共需要输入四个数，输入的n代表的是这个数组的长度，q代表的是查询的次数，l 和 r代表的是下标，输出的是数组arr[l] + …… + arr[r]。
那么这里就是有疑问的，题目描述的为什么是从a[1]到a[n]？而不是从arr[0]开始呢？
这里是为了防止边界，我们在算法原理部分介绍。
我们首先思考暴力解法，暴力解法无非就是模拟这个相加的过程，那么时间复杂度是查询次数 * （l - r + 1），所以最坏的情况就是l是1，r是n，所以时间复杂度就是q * n。
在这里，时间肯定是过不了的，因为题目要求：
所以q * n的话，时间复杂度是10^5，放在任何一道编程题都是过不去的。
那么我们的前缀和算法就闪亮登场了。
算法原理
这道题目我们使用的是前缀和数组，那么什么是前缀和呢？
前缀和数组，无非就是dp[i]代表的是从arr[0]一直加到arr[i]，这个数组的使用在这里已经很接近我们使用该数组的本意了。
使用该数组为了简化我们暴力遍历数组这个过程。
那么对于l r来说，我们要求的是arr[l] + …… + arr[r]，所以这个过程我们可以使用前缀和数组简化成dp[r] - dp[l - 1]，那么这个过程是O(1)的，也就是整体下来时间复杂度是q的。
但是为什么索引是从1开始的呢？这是为了处理边界情况，如果我们要求的是 0 2这个区间，那么l - 1的值就是-1，对于一个数组来说肯定是访问不了-1的，所以这道题是从1开始的。
这是一个小细节。
算法编写
#include <iostream>
#include <vector>
using namespace std;
int main()
{
//1.输入数据
int n = 0, q = 0;
cin >> n >> q;
vector<int> arr(n + 1, 0);
for(int i = 1;i <= n; i++)
cin >> arr[i];
//2.预处理前缀和数组
vector<long long> dp(n + 1, 0);
for(int i = 1; i <= n; i++)
dp[i] = dp[i - 1] + arr[i];
//3.使用前缀和数组
int l = 0, r = 0;
while(q--)
{
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}但是这道题目有个坑就是，如果两个整型相加可能会导致溢出的问题，所以dp数组使用的long long类型。
这是一维数组的模板，下一道题目是二维数组的模板。
二维数组的前缀和
题目解析
题目的要求和一维数组是差不多的，但是并不是从1一直加到n的，而是一个区域：
就像这样，输入的x1 y1 x2 y2是1 1 2 2，那么要求的值就是由这几个下标组成的正方形的值。
当然了，暴力解法的话，肯定是要超时的，所以我们就不予考虑了。
题目的要求我们也是基本清楚了，并且在牛客上的时候，会提示使用lld打印，所以存在溢出的风险，第二个数组就使用long long类型了。
我们就直接介绍二维数组前缀和的算法原理了。
算法原理
对于二维数组前缀和的算法原理部分，同理，我们就需要得到i j对应的区域大小了：
我们如果直接遍历的话，就和暴力解法没有什么区别，所以我们不如拆分一下这个二维数组，对于dp[i][j]来说的话，就是从1 1的位置到i j位置，我们可以划分成四个区域，A B C D，如果单独求A B C的大小并不是很好求的，所以我们不妨变动一下式子，改成A + B + A + C + D - A。
此时A + B就是dp[i - 1][j] A + C 就是等于dp[i][j - 1]，D就是arr[i][j]，A就是dp[i - 1][j - 1]。
得到dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1]。
预处理前缀和数组就结束了，接下来是如何使用的问题。
给的是x1 y1 x2 y2，题目要求的值就是D。同样的，如果我们直接硬求每个区域的值，非常麻烦，所以我们不妨变化一下式子 D = A + B + C + D - (A + B) - (A + C) + A。至于为什么这样干，因为我们发现如果单独求B或者C十分麻烦，所以用来和A结合一下。
此时对于A + B + C + D，就是dp[x2][y2]，对于A + C来说，就是dp[x2][y1 - 1]，对于A + B来说，就是dp[x1 - 1][y2]，A就是dp[x1 - 1][y1 - 1]。
使用前缀和结束了，这道题目也就结束了。
算法编写
#include <iostream>
#include <vector>
using namespace std;
int main()
{
//1.输入数据
int n = 0, m = 0, q = 0;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> arr[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] + arr[i][j] - dp[i - 1][j - 1];
//3.使用前缀和数组
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
while(q--)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;
}
return 0;
}前缀和的模板就介绍完毕了~
感谢阅读！