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）。

不过需要注意，

1. 如果单纯把（i-1，j）和（i，j-1）加起来，那么有一块是重复加了，就是（i-1,j-1）这一块（图中灰色区域），所以要减去它。

2. 这个矩阵还不完整，缺少了途中红色那块，所以我们需要单独把（i，j）这个点加起来。

3. 
   
   

4. 假设第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;  }

(adsbygoogle = window.adsbygoogle || []).push({});