1. 回顾一维数组前缀和

二维数组前缀和是为了更高效率的计算 $x_l + x_{l+1} + ... + x_r$ 而设计的算法。一维数组前缀和算法有 2 个要点：

1. 构造前缀和数组

for(int i=1;i<=n;i++>)
{
    scanf("%d",&x[i]);
    sum[i] = sum[i-1] + x[i];
}

2. 根据起始下标 l 和结束下标 r ，计算 $x_l + x_{l+1} + ... + x_r$ = sum[r] - sum[l-1]

2. 二维数组前缀和

二维数组前缀和算法和一维数组前缀和的思路类似，提前构造好前缀和数组，当需要问某个一个子矩阵之和的时候，通过简单快捷的计算得到答案，减少了 2 层循环。

1. 构造前缀和数组

和一维数组前缀和算法类似，二维数组前缀和也需要构造前缀和数组，不同的是，二维数组的前缀和数组也是二维的。我们用 sum[i][j] 来记录 $x_{1,1} + x_{1,2} + ... x_{1,j} + x_{2,1} + x_{2,2} + ... + x_{2,j} + ... + x_{i,1} + x_{i,2} + ...+ x_{i,j}$ ，也就是下图先蓝色区域的数字之和。

为了方便在计算机程序中，我们把这个区域的求和过程做成基于递推算法，它的值通过下面的方式进行计算：

根据前缀和数组的定义，上图中黄色底色的这个区域相当于 sum[i-1][j] , 浅蓝色的区域相当于 sum[i][j-1] , 橘红色的这一个格子就是 x[i][j] , 灰色底色的区域相当于 sum[i-1][j-1]，因此递推的公式是：

sum[i][j] = sum[i-1][j] + sum[i][j-1] + x[i][j] - sum[i-1][j-1]

for(int i=1;i<=n;i++>)
{
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&x[i][j]);
        sum[i][j] = sum[i-1][j] + sum[i][j-1] + x[i][j] - sum[i-1][j-1];
    }
}

2. 计算子矩阵和

假设你要计算从 [a][b] （左上角） 到 [a2][b2] （右下角） 子矩阵之和，如果按照传统方法，代码是这样写的

int s=0;
for(int i=a;i<=a2;i++)
    for(int j=b;j<=b2;j++)
        s += x[i][j];

基于二维数组前缀和算法，代码可以简化为：

s = sum[a2][b2] - sum[a1-1][b2] - sum[a2][b1-1] + sum[a1-1][b1-1];

上面的公式，基于图解来理解，就是下图：

3. 例题

题目描述

读入一个 N 行 M 列的二维数组，然后有求一个边长是 L 的子正方形，要求里面的数字和最大，输出这个最大值。

输入格式

第一行 3 个正整数：N、M、L，L <= N, L <= M

下面 N 行，每行 M 个整数 $a_{i,j}$。

提示：数据比较多，建议使用 scanf 读入。

数据范围

1 <= N , M , L <= 2000
L <= N
L <= M
-1000 <= $a_{i,j}$ <= 1000

输出格式

1 个整数，表示最大值。

样例

3 5 3
-8 -2 -3 4 -5
4 5 -1 7 6
-1 8 9 0 -2

27

程序填空

#include<bits/stdc++.h>
using namespace std;
long long sum[2001][2001];
int main()
{
	int n,m,l,i,j,ii,jj,t;
	long long ans=-100000000000000000,s;
	scanf("%d %d %d",&n,&m,&l);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%d",&t);
			sum[i][j] = sum[i-1][j] + sum[i][j-1] + 填空(1) - 填空(2);
		}
	}

	for(i=1;i+l-1<=n;i++)
	{
		for(j=1;j+l-1<=m;j++)
		{
			//左上角是(i,j)，计算右下角坐标(ii,jj)
			ii = 填空(3)
			jj = j+l-1;
			
			s = sum[ii][jj] - 填空(4) - sum[i-1][jj] + 填空(5);
			ans = max(ans,s);
		}
	}

	printf("%lld",ans);	

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}