二维前缀和

​ 众所周知，一维前缀和是用o(1)复杂度来处理线性数据区间和的问题的。那二维前缀和就是通过o(1)复杂度来处理子矩阵和问题的好办法。

1、前缀和数组预处理：

​ 一维前缀和数组中pi的意义是a1到ai的和，二维前缀和中pij的意义是a11到aij这个子矩阵的和。p[10][6]的值就是下图中蓝色部分数据的和。

​ 那如何在o(n^2)的复杂度下求得某个坐标的二维前缀和呢？我们在读入的数组的时候，是逐行从左到右读入，就是说对于每一个位置，他的左边和上面都是已经读入了的或是0 。那么我们可以把（1，1）到（i，j）的矩形分成四块：

其中阴影最深的是重叠部分。那么，pi,j = （pi-1,j） + （pi,j-1） - （pi-1,j-1）。

2、计算子矩阵和：

​ 给出左上端点（i，j）和右下端点（u，v），计算出该矩阵的和。

根据上图可以发现，sum = (pu,v) - (pi-1,v) - (pu,j-1) + (pi-1,j-1) 。

要多加一个左上角是因为有重叠部分多减了一次。

///////////////////////////////////////////////////

Codeforces - 1580A - Portal

题目大意：

​ 5行4列的黑曜石框可以做一个传送门，要求是边上用黑曜石填，中间不填，顶点可以填可以不填。给一个n*m二维矩阵表示现在的黑曜石摆放，问改动最小的子矩阵的改动次数是多少。

思路：

​ n最大是400，用二维前缀和去做复杂度是n^4 。我们只要算出每一个子矩阵中间有几个1 ，边上有几个0就可以得到答案。但是运算次数会到2e10，十分危险。所以我们要考虑一下一些情况是没有必要继续进行循环的，比如说我们在扩大子矩阵的右边的过程中发现值已经超过了ans，那继续扩大，值是不可能变小的，所以不用继续循环下去。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const ll N = 2*1e6+1000;
const ll mod = 1e9 + 7 ;

/////////////////////////////////////////////////

int p[500][500] ;

int get(int i , int j , int u , int v){//计算子矩阵和
	return p[u][v] - p[u][j - 1] - p[i - 1][v] + p[i - 1][j - 1] ;
} 

void solve(){
	
	int n , m , ans = INF ;
	scanf("%d %d", &n , &m ) ;
	getchar() ;
	
	for(int i = 1 ; i <= n ; i ++ , getchar() )
	for(int j = 1 ; j <= m ; j ++){
		char chr = getchar() ;
		p[i][j] = chr - '0' + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] ;	
	}
	
	for(int i = 1 ; i <= n ; i ++ )
	for(int j = 1 ; j <= m ; j ++ )
	for(int u = i + 4 ; u <= n ; u ++ )
	for(int v = j + 3 ; v <= m ; v ++ ){
					
		int ctr = get(i + 1 , j + 1 , u - 1 , v - 1 ) ;
		int  up = v - j - 1 - get(i , j + 1 , i , v - 1 ) ;
		int  dw = v - j - 1 - get(u , j + 1 , u , v - 1 ) ;
		int lft = u - i - 1 - get(i + 1 , j , u - 1 , j ) ;
		int rit = u - i - 1 - get(i + 1 , v , u - 1 , v ) ;
					
		if(ans <= ctr + dw + lft )break ;
					
		ans = min(ans , ctr + up + dw + lft + rit) ;
	
	}
	
	printf("%d\n" , ans );
}

int main(){
	
	ios::sync_with_stdio(false) ;
	//freopen("inn.in","r",stdin) ;
	int T;
	scanf("%d" , &T);
	while(T -- )solve() ;
		
}