二维前缀和的经典例题

二维前缀和就是用一个点去代替一个矩形，查询时间是O（1）
公式 sum[ i ][ j ] = map[ i ][ j ]+sum[ i-1 ][ j ]+sum[ i ][ j-1 ]-sum[ i-1 ][ j-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;
        }
        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];
                ans = max(ans, cnt);
            }
        printf("%d\n", ans);
    }
    return 0;
}