二维前缀和

公式

$$S_{i,j}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{i,j}$$
$$S=S_{i,j}-S_{a,j}-S_{i,b}+S_{a,b}$$

注意事项

1.内存问题：
由于每次在更新前缀和时只需要用到当前坐标的原数据，因此可以先将原始数据暂存在前缀和数组中，而不需要新开辟一个数组用于存储原始数据。
2.注意题目中的数据范围，对应选择数据类型，以及一些特殊情况的判断。例如此题中，r有可能会大于n，故而进行特判if(r>=N) Max=s[N-1][N-1];
3.在涉及到坐标相关计算的时候，注意找数据验证坐标是否正确，以免造成错误。
4.前缀和相关题目，涉及到下标-1的情况，所以坐标从1开始进行赋值。
5.题目中w是累加值。

题解代码

#include<iostream>

using namespace std;

const int N=5000+10;
int s[N][N];

int main(){
    int n,r;
    cin>>n>>r;
    while(n--){
        int x,y,w;
        cin>>x>>y>>w;
        s[x+1][y+1]+=w;
    }

    for(int i=1;i<N;i++){
        for(int j=1;j<N;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }

    int Max=0; //注意题目中最大值的范围
    if(r>=N) Max=s[N-1][N-1];

    for(int i=r;i<N;i++){
        for(int j=r;j<N;j++){
            Max=max(Max,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);  
        }
    }
    cout<<Max;



    return 0;
}