网站建设合同.doc,专业网站建设最新报价,有没有专门做设计的网站,学做网站看书会了吗作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;要学会在纸上打草稿#xff0c;这个很重要#x1f43e; 文章目录1.什么是前缀和#xff1f;2.怎么求前缀和#xff1f;3.前缀和有什么用#xff1f;4.进阶二维:矩阵和前缀和 主打一个记公式 1.什么是前… 作者指针不指南吗 专栏算法篇 要学会在纸上打草稿这个很重要 文章目录1.什么是前缀和2.怎么求前缀和3.前缀和有什么用4.进阶二维:矩阵和前缀和 主打一个记公式 1.什么是前缀和
原数组 a1 , a2 , a3 , a4 , a5 , a6 , a7 前缀和 s1a1; s2a1a2; s3a1a2a3; … sia1a2a3…ai 前缀和实际就是数组前 i 项和 2.怎么求前缀和
结合定义解释的很清楚前 i 项相加即可
思路第 i 个前缀和就 前一个前缀和 第 i 个元素
但是注意循环开始从1开始,s00; 第一种 易懂但用两个数组
for(int i1;in;i){scanf(%d,a[i]);s[i]a[i];}第二种 优化版只需要一个数组
for(int i1;i;i){scanf(%d,s[i]);s[i]s[i-1];}3.前缀和有什么用
作用只有一个求区间和
求区间使用前缀和可以降低时间复杂度更加方便 求区间[l,r]中元素的和 s [ l ~ r ] s [ r ] - s [ l -1 ] 这里解释了为什么写前缀和的时候从1开始并且s00 通用的对 s[1~ n]也适用 例如,求数组第a个到第b个的子数组的和 while(m--){int a,b;cinab;couts[b]-s[a-1]endl;}4.进阶二维:矩阵和 求黄色部分的子矩阵和 黄整个-绿-蓝混 S[i, j] 第i行j列格子左上部分所有元素的和 以(x1, y1)为左上角(x2, y2)为右下角的子矩阵的和为 S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] S[x1 - 1, y1 - 1] 代码实现
#includeiostream
using namespace std;const int N1010;int s[N][N];int n,m,q;int main(){cinnmq;for(int i1;in;i)for(int j1;jm;j){cins[i][j];s[i][j]s[i-1][j]s[i][j-1]s[i-1][j-1];}while(q--){int x1,y1,x2,y2;cinx1y1x2y2;couts[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1];}return 0;
}
