题目描述

有一个n行m列的矩阵，对于向其输入的每个操作，对其表示的左上角坐标和右下角坐标中间的子矩阵每个元素都加上数值c；最后输出所有修改操作结束后的矩阵；

样例

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1//矩阵到这里结束
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

算法1

差分矩阵 $O(n*m)$

差分是前缀和的逆运算版本，这里注意自己做的时候在草稿纸上模拟两个映射方式(从a到b和从b到a)；

时间复杂度

C++ 代码

#include<iostream>
using namespace std;

const int N = 1002;
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){
            scanf("%d", &a[i][j]);
            insert(i, j, i, j, a[i][j]);
        }//将建立差分数组的操作合并在数值修改操作中，可在草稿纸上模拟发现是一样的；
    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] = b[i][j] + a[i-1][j] + a[i][j-1] -a[i-1][j-1]; //前缀和重新加起来，是建立前缀和数组的步骤
            cout<<a[i][j]<<' ';
        }
        printf("\n");
    }
    return 0;
}