思路

1. 构建二维差分
   • 以二维前缀和形式构造
   • 以二维差分形式构造
2. 用二维差分
   • …
3. 还原数组
   • 二维前缀和思想还原

c++

版本1（二维前缀和形式构造差分数组）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N];
int b[N][N];

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
            //构建二维差分
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    }
    while(q--){
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        //用二维差分
        b[x1][y1]+=c;
        b[x1][y2+1]-=c;
        b[x2+1][y1]-=c;
        b[x2+1][y2+1]+=c;
    }
    //二维前缀和还原数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            a[i][j]=a[i-1][j]+a[i][j-1]+b[i][j]-a[i-1][j-1];
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

版本2（二维差分形式构造差分数组）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N];

void insert(int x1,int y1,int x2,int y2,int c){
    a[x1][y1]+=c;
    a[x2+1][y1]-=c;
    a[x1][y2+1]-=c;
    a[x2+1][y2+1]+=c;
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            int x;
            scanf("%d",&x);
            //构建二维差分
            insert(i,j,i,j,x);
        }
    }
    while(q--){
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        //用二维差分
        insert(x1,y1,x2,y2,c);
    }
    //二维前缀和还原数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1];
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

java

import java.util.*;
import java.io.*;
public class Main{
    static int N=1010;
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
        String[] s1=br.readLine().split(" ");
        int n=Integer.parseInt(s1[0]),m=Integer.parseInt(s1[1]),q=Integer.parseInt(s1[2]);
        int[][] arr=new int[N][N];
        for(int i=1;i<=n;i++){
            String[] s2=br.readLine().split(" ");
            for(int j=1;j<=m;j++) arr[i][j]=Integer.parseInt(s2[j-1]);
        }
        int[][] c_f=new int[N][N];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) insert(c_f,i,j,i,j,arr[i][j]);
        }
        while(q>0){
            q--;
            String[] s3=br.readLine().split(" ");
            int x1=Integer.parseInt(s3[0]),y1=Integer.parseInt(s3[1]),x2=Integer.parseInt(s3[2]),y2=Integer.parseInt(s3[3]),c=Integer.parseInt(s3[4]);
            insert(c_f,x1,y1,x2,y2,c);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) c_f[i][j]+=c_f[i-1][j]+c_f[i][j-1]-c_f[i-1][j-1];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) pw.print(c_f[i][j]+" ");
            pw.println();
        }
        pw.flush();
    }
    public static void insert(int[][] arr,int x1,int y1,int x2,int y2,int c){
        arr[x1][y1]+=c;
        arr[x2+1][y1]-=c;
        arr[x1][y2+1]-=c;
        arr[x2+1][y2+1]+=c;
    }
}