AcWing 798. 差分矩阵【 c++详细题解】

矫情吗；* 2021-07-24 22:28 449阅读 0赞

### 题目 ###

输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。  
**输入格式**

第一行包含整数n,m,q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。  
**输出格式**

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。  
数据范围

1≤n,m≤1000,  
1≤q≤100000,  
1≤x1≤x2≤n,  
1≤y1≤y2≤m,  
−1000≤c≤1000,  
−1000≤矩阵内元素的值≤1000

**输入样例：**

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

**输出样例：**

2 3 4 1  
4 3 4 1  
2 2 2 2

### 2.思路 ###

如果扩展到二维，我们需要让二维数组被选中的子矩阵中的每个元素的值加上`c`,是否也可以达到`O(1)`的时间复杂度。答案是可以的，**考虑二维差分**。

`a[][]`数组是`b[][]`数组的前缀和数组，那么`b[][]`是`a[][]`的差分数组

原数组： `a[i][j]`

我们去构造差分数组： `b[i][j]`

使得`a`数组中`a[i][j]`是`b`数组左上角`(1,1)`到右下角`(i,j)`所包围矩形元素的和。

**如何构造`b`数组呢？**

这里不像一维差分那样，可以直接找到一种构造方式去构造，因此我们可以去**逆向思考**。

同一维差分，我们构造二维差分数组目的是为了 让原二维数组`a`中所选中子矩阵中的每一个元素加上`c`的操作，可以由`O(n*n)`的时间复杂度优化成`O(1)`

已知原数组`a`中被选中的子矩阵为 以`(x1,y1)`为左上角，以`(x2,y2)`为右上角所围成的矩形区域;

**始终要记得，a数组是b数组的前缀和数组**，比如对`b`数组的`b[i][j]`的修改，会影响到`a`数组中从`a[i][j]`及往后的每一个数。

假定我们已经构造好了`b`数组，类比一维差分，我们执行以下操作  
来使被选中的子矩阵中的每个元素的值加上`c`

`b[x1][y1] + = c`;

`b[x1,][y2+1] - = c`;

`b[x2+1][y1] - = c`;

`b[x2+1][y2+1] + = c`;

每次对`b`数组执行以上操作，**等价于：**

for(int i=x1;i<=x2;i++)
      for(int j=y1;j<=y2;j++)
        a[i][j]+=c;

**我们画个图去理解一下这个过程：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

`b[x1][ y1 ] +=c` ; 对应图1 ,让整个`a`数组中**蓝色矩形面积**的元素都加上了`c`。  
`b[x1,][y2+1]-=c` ; 对应图2 ,让整个`a`数组中**绿色矩形面积**的元素再减去`c`，使其内元素不发生改变。  
`b[x2+1][y1]- =c` ; 对应图3 ,让整个`a`数组中**紫色矩形面积**的元素再减去`c`，使其内元素不发生改变。  
`b[x2+1][y2+1]+=c`; 对应图4,让整个`a`数组中**红色矩形面积**的元素再加上`c`，红色内的相当于**被减了两次**，再加上一次`c`，才能使其恢复。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]  
**我们将上述操作封装成一个插入函数:**

void insert(int x1,int y1,int x2,int y2,int c)
    {      //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }

我们可以先假想`a`数组为空，那么`b`数组一开始也为空，但是实际上`a`数组并不为空，因此我们每次让以`(i,j)`为左上角到以`(i,j)`为右上角面积内元素(其实就是一个小方格的面积)去插入 `c=a[i][j]`，等价于原数组`a`中`(i,j)` 到`(i,j)`范围内 加上了 `a[i][j]` ,因此执行`n*m`次插入操作，就成功构建了差分`b`数组.

**这叫做曲线救国。**

**代码如下：**

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

**总结：**

![在这里插入图片描述][20201217172035975.png]

### 3.代码 ###

include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1e3+10;
    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--)
      { 
          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++)
          { 
              printf("%d ",b[i][j]);
          }
          printf("\n");
      }
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/08c7b54038bf46b4b3f630f36d00da3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/6e5c6a39213c480b85046bad893c5ebe.png
[20201217172035975.png]: /images/20210724/6d6b4c58eb2d4ba4835c9f91dd31dcf1.png