描述

给一个长度为$nn$的数组$aa$，$mm$次操作，左上角为$(x_1,y_1)(x\_1,y\_1)$，右下角为$(x_2,y_2)(x\_2,y\_2)$加$kk$，问$mm$次操作后的数组

思路

• 差分模板题，由于仅有一次查询，因此可以利用前缀和的性质，设数组$sumsum$表示$mm$次操作后，每个位置增加的数为多少，则每次操作将$sum[x_1][y_1]+ksum[x\_1][y\_1]+k$，$sum[x_2+1][y_1]-ksum[x\_2+1][y\_1]-k$,$sum[x_1][y_2+1]-ksum[x\_1][y\_2+1]-k$,$sum[x_2+1][y_2+1]+ksum[x\_2+1][y\_2+1]+k$，最后对数组$sumsum$求二维前缀和

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+5;
ll a[MAXN][MAXN],sum[MAXN][MAXN];
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);
    while(q--)
    {
        int x1,x2,y1,y2,k;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
        sum[x1][y1]+=k;
        sum[x2+1][y2+1]+=k;
        sum[x2+1][y1]-=k;
        sum[x1][y2+1]-=k;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            a[i][j]+=sum[i][j];
        }
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++)
            printf("%lld ",a[i][j]);
}

时间复杂度$O(nm)O(nm)$，空间复杂度$O(nm)O(nm)$