【算法】前缀和与差分(3)二维数组前缀和
0.前言
前面的一篇文章，介绍了一维数组的前缀和，这篇文章中，介绍一下二维数组的前缀和
1.定义
二维数组的前缀和就是按照二维数组求和。公式如下：
那二维前缀和中一个f[i][j]表示的意思就是
以（1,1）为左上角以（i,j）为右下角这个矩阵里面数的和，可以用下面的这个图表示
f[i][j]就是红色框的部分。
举个例子：
1 2 4 3 5 1 2 4 6 3 5 9
如果按照公式进行计算，结果是：
1 3 7 10 6 9 15 22 12 18 29 45
把上面这个图扩大
我们要求(i,j)， （i,j）可以由两部分块构成 (i-1,j) 和 （i，j-1）。
不过需要注意，
如果单纯把（i-1，j）和（i，j-1）加起来，那么有一块是重复加了，就是（i-1,j-1）这一块（图中灰色区域），所以要减去它。
这个矩阵还不完整，缺少了途中红色那块，所以我们需要单独把（i，j）这个点加起来。
假设第i行第j列对应的数组为aij ,对应的二维前缀和为sumij 。基于容斥原理，那么
sumi,j = sum i-1,j + sum i,j-1 - sum i-1,j-1 + ai,j sum[i,j] =sum[i-1,j] + sum[i,j-1] -sum[i-1,j-1] +a[i,j]
【参考代码】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+2;
const int MAXM = 1e3+2;
int sum[MAXN][MAXM] = {};
int main() {
int n,m,r,c;
cin>>n>>m;//>>r>>c;
int data;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin >> data;
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+data;
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cout << sum[i][j] << " ";
}
cout << endl;
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
