二维前缀和（整理）

概念

二维前缀和，建立在一维前缀和之上，如果我们要求一个矩阵内一个任意子矩阵的数的和，那么就可以用二维前缀和。

详解

类比一维前缀和，我们可以在O(n)的时间复杂度下预处理，如下代码：

s[i]=s[i-1]+a[i];

那么对于二维前缀和，我们怎么预处理呢？

先给出算式：

Map[i][j]+Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1]+a[i][j];

（a数组是原数据数组，Map数组用于存放前缀和）

类比一维前缀和，因为我们从左到右在计算a[i]的时候已经知道了a[i−1]的值，所以同理，我们从左上向右下在计算Map[i][j]的时候已经知道了它右上所有点的前缀和，也就是知道Map[i−1][j]、Map[i][j−1]和Map[i−1][j−1]的值，那么现在考虑为什么要做如上的运算。

其中，Map[i][j]的初始值即为点(i,j)的权值，如图： 那么现在，我们要求前缀和，也就是要加上下图中橙色区域： 而我们加上的Map[i−1][j]即为下图蓝色区域： 加上的Map[i][j−1]即为下图绿色区域： 然后我们会发现，有一部分重叠了，如下图紫色区域： 而这部分就是我们要减去的Map[i−1][j−1]。 那么我们的预处理就完成了。 时间复杂度：O(n×m)，与一维中的O(n)预处理同理。

求二维前缀和

假设我们需要计算（x，y）的前缀和，如下图所示。 图中我们标注出三个点。

红色点表示（x，y）前缀和，用sum[x][y]表示。
蓝色表示（x，y-1）前缀和，用sum[x][y-1]表示。
黄色表示（x-1，y）前缀和，用sum[x-1][y]表示。
紫色表示（x-1，y-1）前缀和，用sum[x-1][y-1]表示。

样例

题解

#include <bits/stdc++.h> 
using namespace std; 
const int MAXN = 1e3+2; 
int sum[MAXN][MAXN] = {};
 
int main() {
	int n,m; 
	cin>>n>>m;  
	int data;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin >> data;
			//假设第 i 行第 j 列对应的数组为ai,j，对应的二维前缀和为sumi,j，基于容斥原理
			//sumi,j=sumi-1,j+sumi,j-1?sumi-1,j-1+ai,j
			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;
}