[练习](一二维 )前缀和 与 差分

[练习](一二维 )前缀和 与 差分

目录

​​AcWing 795. 前缀和​​

​​AcWing 796.子矩阵的和 ​​

​​AcWing 797.差分​​

​​AcWing 798.差分矩阵​​

AcWing 795. 前缀和

输入样例：

5 32 1 3 6 41 21 32 4

输出样例：

3610

#include #include #include using namespace std;const int N = 1e5+10;int a[N];int main(){ int n,m; cin >> n >> m; for (int i = 1; i <= n; i ++ ){ scanf("%d", &a[i]); a[i] += a[i-1]; } int l,r; for (int i = 0; i < m; i ++ ){ scanf("%d%d", &l, &r); cout << a[r]-a[l-1] << endl; } return 0;}

AcWing 796.子矩阵的和

输入样例：

3 4 31 7 2 43 6 2 82 1 2 31 1 2 22 1 3 41 3 3 4

输出样例：

172721

#include #include #include using namespace std;const int N = 1010;int a[N][N],s[N][N];int main(){ int n,m,x; cin >> n >> m >> x; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ){ scanf("%d", &a[i][j]); s[i][j] += s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; } int x1,x2,y1,y2; while (x -- ) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); cout << s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1] <

AcWing 797.差分

输入样例：

6 31 2 2 1 2 11 3 13 5 11 6 1

输出样例：

3 4 5 3 4 2

#include #include #include using namespace std;const int N = 1e5+10;int a[N],b[N];int main(){ int n,m; cin >> n >> m; for (int i = 1; i <= n; i ++ ){ scanf("%d", &a[i]); b[i]=a[i]-a[i-1]; } int l,r,add; for (int i = 0; i < m; i ++ ){ scanf("%d%d%d", &l, &r, &add); b[l] += add; b[r+1] -= add; } for (int i = 1; i <= n; i ++ ){ b[i] += b[i-1]; printf("%d ",b[i]); } return 0;}

AcWing 798.差分矩阵

输入样例：

3 4 31 2 2 13 2 2 11 1 1 11 1 2 2 11 3 2 3 23 1 3 4 1

输出样例：

2 3 4 14 3 4 12 2 2 2

#include #include #include using namespace std;const int N = 1010;int a[N][N],b[N][N];void change(int x1,int y1,int x2,int y2,int add){ b[x1][y1] += add; b[x1][y2+1] -= add; b[x2+1][y1] -= add; b[x2+1][y2+1] += add;}int main(){ int n,m,x; cin >> n >> m >>x; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ){ scanf("%d", &a[i][j]); change(i,j,i,j,a[i][j]); } int x1,x2,y1,y2,add; for (int i = 0; i < x; i ++ ){ scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &add); change(x1, y1, x2, y2, add); } for (int i = 1; i <= n; i ++ ){ for (int j = 1; j <= m; j ++ ){ b[i][j] += b[i-1][j]+b[i][j-1]-b[i-1][j-1]; cout << b[i][j] << ' '; } cout << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。