【C++】 二维差分数组 Acwing798. 差分矩阵

【C++】 二维差分数组 Acwing798. 差分矩阵

目录

Acwing 798.差分矩阵

1、题目链接

2、题目

3、思路核心+灵魂画手

 4、AC代码

---

Acwing 798.差分矩阵

1、题目链接

Acwing 798.差分矩阵

2、题目

3、思路核心+灵魂画手

思路：1、创建原二维数组a       构建差分二维数组b

           2、再进行二维前缀和还原数组  差分和前缀和为逆运算   

           3、输出

核心 ：

void insert (int x1,int y1,int x2,int y2,int value) {
    b[x1][y1]+=value;  
    b[x1][y2+1]-=value;
    b[x2+1][y1]-=value; //加1是为了不改变 x2 y2 点的值
    b[x2+1][y2+1]+=value;
}

代码如果看的有点懵可以看下面的图  【看不懂别说是我画的233】

 颜色表示对应面积  圆表示点  矩形表示该区域内的点

 4、AC代码

#include  

using namespace std;

const int N=1010;

int n,m,q;
int a[N][N],b[N][N];

//二维/矩阵 差分核心
void insert (int x1,int y1,int x2,int y2,int value) {
    b[x1][y1]+=value;  
    b[x1][y2+1]-=value;
    b[x2+1][y1]-=value; //加1是为了不改变 x2 y2 点的值
    b[x2+1][y2+1];
}

int main () {
    scanf("%d%d%d",&n,&m,&q);

    for (int i = 1;i <= n;++ i)
        for (int j = 1;j <= n;++ j)
        scanf("%d",&a[i][j]);

    for (int i = 1;i <= n;++ i)
        for (int j = 1;j <= n;++ j)
            insert(i,j,i,j,a[i][j]);//构建二维差分数组

    while (q --) {
        int x1,x2,y1,y2,value;
        cin>>x1>>y1>>x2>>y2>>value;
        insert (x1,y1,x2,y2,value);
    }
      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++) {
            printf("%d ", b[i][j]);
        }
        printf("n");
    }
    return 0;
}