发卡平台网站建设,可信赖的深圳网站建设,网站前台后台模板,装修推荐平台#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前正在学习c和算法 ✈️专栏#xff1a;【C/C】算法 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有… 个人主页Weraphael ✍作者简介目前正在学习c和算法 ✈️专栏【C/C】算法 希望大家多多支持咱一起进步 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 目录一、一维前缀和1.1 什么是一维前缀和1.2 如何求Sn1.3 用途1.4 代码模板1.5 细节问题二、二维前缀和2.1 用途2.2 前缀和S[i][j]求法2.3 子矩阵求法2.4 代码模板三、总结一、一维前缀和
1.1 什么是一维前缀和 前缀和就是新建一个数组数组中保存的是原数组前n项的和 【举个例子】
Sn a1a2a3…an Sn就是数列的前缀和下标一定要从1开始后面会讲解原因 1.2 如何求Sn
我们可以利用上面的图来找找规律 S1 a1S2 a1 a2 S1 a2S3 a1 a2 a3 S2 a3S4 a1 a2 a3 a4 S3 a4S5 a1 a2 a3 a4 a5 S4 a5这一套下来前缀和的公式很明显就是Si Si-1 ai
【代码】
for (int i 1;i n;i)
{s[i] s[i-1] a[i];
}1.3 用途 能快速求出数列中某一段的和时间复杂度为O(1) 还是要利用这幅图 假设我们要计算原数组a中区间[2,4]的和我们就可以用S4 - S1 总结假设日后题目要求区间[l,r]的和其实也能循环遍历不过时间复杂度是O(N)而前缀和的时间复杂度是O(1)计算区间[l,r]的和其公式为Sr - Sl-1
1.4 代码模板
#include iostream
using namespace std;const int N 100010;
int a[N],s[n];int main()
{int n; //n - 原数组元素的个数scanf(%d,n);//输入原数组for (int i 1;i n;i) {scanf(%d,a[i]);}//前缀和公式for (int i 1;i n;i){s[i] s[i - 1] a[i];}//以下是计算某段区间的和int l,r;scanf(%d%d,l,r);printf(%d\n,s[r] - s[l - 1]);return 0;
}1.5 细节问题 首先下标从1开始就是为了定义S0就拿前缀和公式来说S[i] S[i-1] a[i]当i 1时出现了S0而S0要及时置为0原因是为了统一。举个例子假设要计算区间[1,10]之间的和明眼就能看出是要计算S10而为了达到统一计算的效果S10 - S0 S10 - 0.为什么我在代码中没有定义S[0]0原因是我将s[N]定成了全局变量而全局变量有一个特点默认初始化为0 二、二维前缀和
2.1 用途 目的是求出一个矩阵中某一个小矩阵的和 2.2 前缀和S[i][j]求法
大家画图可能会更加容易理解点假设点ij在矩阵的正中心S[i][j] 即为黄色部分所有数的的和 我们可以分三步求出黄色部分的和
第一步先求出红色部分所有数的和 列出式子S[i][j] S[i][j-1] ... 第二步再求出绿色部分所有数的和 列出式子S[i][j] S[i][j-1] S[i-1][j] ... 第三步去重因为前两部重复加上了黑色部分所有数的和因此要减掉一次 最后别忘了加上了本身a[i][j] 列出式子S[i][j] S[i][j-1] S[i-1][j] - S[i-1][j-1] a[i][j] 2.3 子矩阵求法 假设要求左上角为x1y1右下角为x2y2所围成黄色部分所有数的和 子矩阵的求法和求S[i][j]是类似的四步走
第一步先求出红色部分围成所有数的和 列出式子S S[x2][y2] - ... 第二步在用上一步红色部分减去绿色部分所有数的和 列出式子S S[x2][y2] - S[x1 - 1][y2] - ... 第三步再减去灰色部分所有数的和 列出式子S S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] ... 第四步去重因为前两部重复减去了紫色部分所有数的和因此要加上一次 列出式子S S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1] 2.4 代码模板
#include iostream
using namespace std;const int N 10010;
int n, m;
int a[N][N],s[N][N];int main()
{scanf(%d%d%d, n, m); //n -行 m - 列//输入数组for (int i 1; i n; i )for (int j 1; j m; j )scanf(%d, a[i][j]);//二维前缀和公式for (int i 1; i n; i )for (int j 1; j m; j )s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j];//求子矩阵int x1, y1, x2, 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;
}
三、总结
其实大家只要背下前缀和公式就好了
一维前缀和公式S[i] S[i-1] a[i]求某段区间[l,r]: S[r]- S[l-1] 二维前缀和公式S[i][j] S[i][j-1] S[i-1][j] - S[i-1][j-1] a[i][j]求子矩阵公式S S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1]
