前缀和差分+树状数组+线段树-1（前缀和差分）

前缀和即，存在一个数组a,有数组b，b[i]=a[1]+a[2]+...+a[i],从而用O（1）的复杂度求区间和

而差分就是前缀和的逆运算，对与一个数组d[100],d[i]=a[i]-a[i-1],差分可以通过单点更新来实现区间更新

因为差分具有一个性质，也就是把序列A的区间[L,R]加上一个常数d，也就是把AL，AL+1...AR都加上d，其实就是它的差分序列B中，BL+d，BR+1-d，其他位置保持不变即可。利用差分这个性质即可实现快速的序列区间更新。2<=i,j<=n

下图是二维前缀和原理

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<string>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
const int eps=1e-10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn=5010;

int g[maxn][maxn];
int main()
{
    int n,r;
    cin>>n>>r;
    int a=r,b=r;
    for(int i=0,x,y,v;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&v);
        x++,y++;
        a=max(a,x),b=max(b,y);
        g[x][y]=+v;
        
     } 
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
    int res=0;
    for(int i=r;i<=a;i++)
        for(int j=r;j<=b;j++)
            res=max(res,g[i][j]-g[i][j-r]-g[i-r][j]+g[i-r][j-r]);
    cout<<res<<endl;
    return 0;
}