目录
前言:
一维数组的前缀和
题目解析
算法原理
算法编写
二维数组的前缀和
题目解析
算法原理
算法编写
前言:
本文的主题是前缀和,通过两道题目讲解,一道是一维数组的模板,一道是二维数组的模板。
链接分别为:
【模板】前缀和_牛客题霸_牛客网
【模板】二维前缀和_牛客题霸_牛客网
题目分为三个部分讲解,一是题目解析,二是算法原理,三是算法编写,那么,话不多说,直接进行主题咯。
一维数组的前缀和
题目解析
题目看起来是较为复杂的,一共需要输入四个数,输入的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;
}
前缀和的模板就介绍完毕了~
感谢阅读!