798.差分矩阵

简谈

知识点: 前缀和,差分
难点: 理解如何构造差分数组,以及如何输出修改后的数组

时间复杂度

$O(n^2)$

C++ 代码

#include<iostream>

const int N = 1010;

int a[N][N],d[N][N];

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("%d",&a[i][j]);
            //(d[][]的前缀和数组是原数组a[][]) 
            //a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+d[i][j] => 初始化差分数组
            d[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);
        d[x1][y1]+=c;
        d[x1][y2+1]-=c;
        d[x2+1][y1]-=c;
        d[x2+1][y2+1]+=c;
    }

    //打印修改后的矩形
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            //利用 差分数组的前缀和数组是原数组,求a[][]等于求前缀和
            a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }

}