二维前缀和

1.预处理

首先要计算左上角坐标为（x1,y1）右下角坐标为（x2,y2）的矩形内数据的和要先进行预处理

目的是为了得出从（1,1）到（i，j）的矩形内数据的和的公式

即sum[ i ][ j ]=sum[ i-1 ][ j ]+sum[ i ][ j-1 ]-sum[ i-1 ][  j-1]+a[ i ][ j ];

2.得公式 

经过预处理之后我们就可以进行计算

 最后我们得出此矩阵的和为：

      sum[ x2 ][  y2 ] - sum[ x2 ][ y1-1 ]-sum[ x1-1 ][ y2 ]+sum[ x1-1 ][ y1-1 ];

注意：因为我们在预处理和最后得出公式的时候，在sum的下标中都有[ x1-1 ]或者[ y1-1 ],所以我们在读取整个矩阵时行列坐标均从1开始而非0。

接下来是一道二维前缀和的入门题目

最大加权矩形 - 洛谷

和我自己做这道题时的代码

#include<stdio.h>
#include<math.h>
#define N 130
int a[N][N];
int sum[N][N];
int max=0,p=0;
int main()
{
	int n;
	scanf("%d",&n);
	int i=0,j=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
            //这里是预处理，得出sum[i][j]的计算公式。
		}
	}
	int x1,y1,x2,y2;
    //这里要用四个变量循环判断坐标。x1和y1是矩形的左上角坐标，x2和y2是矩形的右上角坐标
	for(x1=1;x1<n;x1++){
		for(y1=1;y1<n;y1++){
			for(x2=x1;x2<=n;x2++){
				for(y2=y1;y2<=n;y2++){
					p=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
					max=(max>p?max:p);
                    //从这些矩阵和中挑出一个最大值
				}
			}
		}
	}
	printf("%d",max);
	return 0;
}