二维前缀和的简单介绍

二维前缀和顾名思义，用一个点去代表一个矩形，查询的时间是O（1）

先给出递推公式 sum[ i ][ j ] = map[ i ][ j ]+sum[ i-1 ][ j ]+sum[ i ][ j-1 ]-sum[ i-1 ][ j-1 ]

看图就知道了，sum[i][j] 表示的是蓝区域红区域加黄区域再加右下角那个

sum[i-1][j] 表示的是蓝区域加黄区域，sum[i][j-1] 表示的是蓝区域加红区域
因为蓝区域重复加了所以要减掉他。

题目——激光炸弹

题目描述
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
若目标位于爆破正方形的边上，该目标将不会被摧毁。

输入描述:
输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。
输出描述:
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

输入

2 1
0 0 1
1 1 1

输出
1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e3 + 5;
int a[maxn][maxn];
int main()
{
   
    int n, r, x, y, v;
    while (~scanf("%d%d", &n, &r))
    {
   
        for (int i = 1; i <= n; ++i)
        {
   
            scanf("%d%d%d", &x, &y, &v);
            a[x + 1][y + 1] = v;
            //因为前缀和求和一般都是从1开始遍历，所以我们这里需要加上一个1，防止数组越界访问
        }
        for (int i = 1; i < maxn; ++i)
            for (int j = 1; j < maxn; ++j)
                a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; //求前缀和把对应矩形的面积求出来
        int ans = 0;
        for (int i = r; i < maxn; ++i)
            for (int j = r; j < maxn; ++j)
            {
   
                int cnt = a[i][j] - a[i - r][j] - a[i][j - r] + a[i - r][j - r];
                //这里循环开始都是从r开始，因为题目给出的爆破范围是r，所以我们求的就是不同位置但是相同面积的矩形内最大价值
                //公式中不管i，j如何变化，始终保持所求得的面积都是r*r，我们只需要在每次求出的价值中更新一个最大价值就是解
                ans = max(ans, cnt);
            }
        printf("%d\n", ans);
    }
    return 0;
}