C++ 二维差分解决矩阵区间更新问题

题目描述

小羊肖恩最近喜欢上了投球游戏，但他已经不满足只有一行球筐的玩法了。

具体来说，在他面前摆放了 n×m 个球筐，这些球筐形成了一个 n×m 的矩阵，整数 ai,j 表示第 i 行第 j 列的球筐最开始的球的个数。

接下来小羊会进行 q 次操作，每次操作会给出五个整数 x1,y1,x2,y2,c，他会将以 (x1,y1) 为左上角，(x2,y2) 为右下角的球筐矩阵都投入 c 个球。请你输出操作完成之后每个框各有多少个球？

输入格式

第一行输入三个整数 n,m,q，表示球筐矩阵的大小和操作次数。

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

接下来 q 行，每次输入五个整数 x1,y1,x2,y2,c。

数据范围保证：1≤q≤10^5，1≤n,m≤10^3，1≤x1≤x2≤n，1≤y1≤y2≤m，1≤ai,j,c≤10^5。

输出格式

输出 n 行，每行 m 个数，表示操作完毕后每个球筐里球的个数。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+10;
int a[N][N],diff[N][N];

int main()
{
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   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];
           diff[i][j]+=a[i][j];
           diff[i][j+1]-=a[i][j];
           diff[i+1][j]-=a[i][j];
           diff[i+1][j+1]+=a[i][j];
       }
   }
   while(q--){
       int x1,y1,x2,y2,c;
       cin>>x1>>y1>>x2>>y2>>c;
       diff[x1][y1]+=c;
       diff[x1][y2+1]-=c;
       diff[x2+1][y1]-=c;
       diff[x2+1][y2+1]+=c;
   }
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+diff[i][j];
       }
   }
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           cout<<a[i][j]<<' ';
       }
       cout<<'\n';
   }
   return 0;
}

核心知识点：二维差分

二维差分数组是一种用于记录矩阵局部区域的变化的数组。设有一个矩阵 a，我们定义差分数组 s 如下：

si,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1

这里的差分数组记录了从矩阵的 (1,1) 到 (i,j) 的矩形区域所发生的变化。

对于本题，我们需要在一个子矩阵中同时修改多个格子的值。差分数组的优势在于，我们可以通过修改差分数组的边界值，来实现对子矩阵内所有格子的值的同时修改。

具体地，当我们需要给子矩阵 (x1,y1) 到 (x2,y2) 中的每个格子都加上 c 时，我们可以对差分数组进行如下操作：

1. sx1,y1+=c
2. sx1,y2+1−=c
3. sx2+1,y1−=c
4. sx2+1,y2+1+=c

经过这样的操作，我们实际上在差分数组中标记了一个子矩阵区域的变化。最后，我们需要根据差分数组恢复原矩阵，以得到最终每个格子的球的个数。

恢复原矩阵的方法如下：

ai,j=ai−1,j+ai,j−1−ai−1,j−1+si,j

可以看到，恢复原矩阵的过程是通过累加差分数组的值来完成的。

注意检查代码末尾分号是否存在，确保输入法处于英语模式且无语法错误。