当前位置：首页 > C++目录 > 正文内容

【算法】前缀和与差分(3)二维数组前缀和

亿万年的星光3年前 (2022-12-10)C++目录2942

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列对应的数组为a_ij,对应的二维前缀和为sum_ij 。基于容斥原理，那么

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;
}