Two dimensional prefix and

1. Preprocessing

First, calculate the upper left coordinate as （x1,y1） The coordinates in the lower right corner are （x2,y2） The sum of the data in the rectangle You have to preprocess first

The purpose is to get from （1,1） To （i,j） The formula of the sum of the data in the rectangle

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

2. Get the formula  

After preprocessing, we can calculate

  Finally, we conclude that the sum of this matrix is ：

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

Be careful ： Because when we preprocess and finally get the formula , stay sum In the subscript of [ x1-1 ] perhaps [ y1-1 ], So when we read the whole matrix, the row and column coordinates are from 1 Start instead of 0.

Next is an introduction to the two-dimensional prefix and

Maximum weighted rectangle - Luogu

And the code when I did this problem myself

#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];
            // Here is pretreatment , obtain sum[i][j] Calculation formula .
		}
	}
	int x1,y1,x2,y2;
    // Here we need to use four variables to judge the coordinates .x1 and y1 Is the coordinate of the upper left corner of the rectangle ,x2 and y2 Is the coordinate of the upper right corner of the rectangle 
	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);
                    // Pick a maximum value from these matrix sums 
				}
			}
		}
	}
	printf("%d",max);
	return 0;
}