题目思路

给定原矩阵a[][],构造差分矩阵b[][]，使得a[][]是b[][]的二维前缀和。

差分核心公式

b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int a[N][N],b[N][N];

//差分函数
void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    //读取矩阵 作为前缀和矩阵
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin>>a[i][j];
    //利用前缀和矩阵 得到 差分矩阵
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i,j,i,j,a[i][j]);
    while(q--)//q次
    {
        int x1,y1,x2,y2,c;
        cin>>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 ++ )
            b[i][j]+=(b[i-1][j]+b[i][j-1]-b[i-1][j-1]);
 //输出
    for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= m; j ++ )
            cout<<b[i][j]<<" ";
        cout<<endl;

        }
    return 0;
}