基本概念

普通(一维，二维)前缀和:

a[1],a[2],a[3].....a[n]
s[i] = a[i] + a[i-1]...a[2] + a[1]

a[3] + a[4]...a[14] + a[15] = s[15] - s[3-1]
s[l,r] = s[r] - s[l-1]

二维前缀和:

假设在一个二维平面上，每个点具有一定的权值，我们要计算点（2，2）到（8，4）的权值和。

首先我们要找到这么几块面积：

我们可以发现，我们所要求的黄色区域，就是黑色 - 绿色 - 粉色 + 青色。

好了，知识都听少的，看例题。

例1激光炸弹

一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。

现在地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个边长为 RR 的正方形的边必须和x，y轴平行。

若目标位于爆破正方形的边上，该目标不会被摧毁。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来NN行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

0<N≤10000
0≤Xi,Yi≤5000

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

题解：

这很明显就是一道二维前缀和的问题了，找区域最值。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5010;
int g[maxn][maxn];

int main(void)
{
    int N,R;
    cin >> N >> R;

    int n = R, m = R;

    for(int i = 0,x,y,w;i < N;++i)
    {
        cin >> x >> y >> w;
        x++,y++;
        n = max(n,x);
        m = max(m,y);
        g[x][y] += w;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1;j <= m; j++)
            g[i][j] += g[i-1][j] + g[i][j-1] - g[i][j];

    int ans = 0;
    for(int i = R;i <= n;i++)
        for(int j = R;j <= m;j++)
            ans = max(ans,g[i][j]-g[i-R][j]-g[i][j-R]+g[i-R][j-R]);

    cout << ans ;

    return 0;
}