二维前缀和
列举一下最近遇到的二维前缀和的题目：
大同小异，可以总结一下模板
注意二维前缀和计算以及运用的共同之处。
最大的和
给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 1×1 或更大的连续子阵列。
矩形的总和是该矩形中所有元素的总和。
在这个问题中，具有最大和的子矩形被称为最大子矩形。
例如，下列数组：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其最大子矩形为：
9 2
-4 1
-1 8
它拥有最大和 15。
输入格式
输入中将包含一个 N×N 的整数数组。
第一行只输入一个整数 N，表示方形二维数组的大小。
从第二行开始，输入由空格和换行符隔开的 N2 个整数，它们即为二维数组中的 N2 个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。
数组中的数字会保持在 [−127,127]的范围内。
输出格式
输出一个整数，代表最大子矩形的总和。
数据范围
1≤N≤100
输入样例：
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
输出样例：
15
#include
using namespace std ;
const int N = 110 ;
int s[N][N] ;
int main()
{
int n ;
cin >> n ;
for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= n ; ++ j)
{
cin >> s[i][j] ;
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1] ;
}
}
int res = -128 ;
for(int x1 = 1 ; x1 <= n ; ++ x1)
{
for(int y1 = 1 ; y1 <= n ; ++ y1)
{
for(int x2 = x1 ; x2 <= n ; ++ x2)
{
for(int y2 = y1 ; y2 <= n ; ++ y2)
{
int ans = s[x2][y2] + s[x1-1][y1-1] - s[x1-1][y2] - s[x2][y1-1] ;
res = max(res , ans) ;
}
}
}
}
cout << res << endl ;
return 0 ;
}
激光炸弹
地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0≤R≤109
0<N≤10000
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1
#include
using namespace std ;
const int N = 5011 ;
int s[N][N] ;
int main()
{
int n , r;
cin >> n >> r;
r = min(r , 5010) ;
int x = r ; int y = r ;
for(int i = 1 ; i <= n ; ++ i)
{
int a , b , c ;
cin >> a >> b >> c ;
s[a+1][b+1] += c ;
x = max(x , a + 1) ; y = max(y , b + 1) ;
}
for(int i = 1 ; i <= x ; ++ i)
{
for(int j = 1 ; j <= y ;++ j)
{
s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1] ;
}
}
int res = 0 ;
for(int i = r ; i <= x ; ++ i)
{
for(int j = r ; j <= y ;++ j)
{
int x1 = i - r + 1 ;
int y1 = j - r + 1 ;
int ans = s[i][j] + s[x1-1][y1-1] - s[x1-1][j] - s[i][y1-1] ;
res = max(res , ans) ;
}
}
cout << res << endl ;
return 0 ;
}
子矩阵的和
输入一个 n 行 m 列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q 行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
#include
using namespace std ;
const int N = 1010 ;
int w[N][N] ;
int main()
{
int n , m , q ;
cin >> n >> m >> q ;
for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= m ; ++ j)
{
cin >> w[i][j] ;
w[i][j] += w[i-1][j] + w[i][j-1] - w[i-1][j-1] ;
}
}
for(int i = 1 ; i <= q ; i ++)
{
int x1 , y1 , x2 , y2 ;
cin >> x1 >> y1 >> x2 >> y2 ;
int res = w[x2][y2] - w[x1-1][y2] - w[x2][y1-1] + w[x1-1][y1-1] ;
cout << res << endl ;
}
return 0 ;
}
总结一下三道题目共同点：
存储前缀和
在计算二维前缀和的时候，在初始化的时候，只有在一个位置只有一个数字的情况下，可以只用一个数组来完成。
例如第一题和第三题，可以只开一个数组节省空间。
但是第二题，细节比较多，因为他是相同位置会有不同的值，所以不可以只用一个数组来进行存储。
利用前缀和
一般都是求矩形内二维元素的和。
我们可以用模板来说明一下。
for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= m ; ++ j)
{
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1] ; //构造二维前缀和的模板
}
}
//比如要计算子矩阵的和，我们的重点应该放在右下角
//例一：遍历任意子矩阵
for(int i = 1 ; i <= x1 ; i ++)
{
for(int j = 1 ; j <= y1 ; ++ j)
{
for(int k = 1 ; k <= x2 ; ++ k)
{
for(int l = 1 ; l <= y2 ; ++l )
{
int res = s[k][l] - s[i-1][l] - s[k][j-1] + s[i-1][j-1] ;
}
}
}
}
//例二：遍历有固定边界的子矩阵
//r为正方形的边长
for(int x2 = r ; x2 <= x ; ++ x2)
{
for(int y2 = r ; y2 <= y ; ++ y2)
{
int x1 = x2 - r + 1 ;
int y1 = y2 - r + 1 ；
int res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] ;//减一的都是x1，这个规律可以记住
}
}
