差分矩阵 | 差分

已知有原数组a，现欲建立差分数组b

建立差分数组的两种方式：

（i）根据原数组建立。b[i] = a[i] - a[i-1]

（ii）在空数组上白手起家：

 1 #include<iostream>
 2 using namespace std;
 3 #define ios_base \
 4     ios::sync_with_stdio(false);\
 5     cin.tie(nullptr),cout.tie(nullptr)
 6 const int N = 1e3+10;
 7 int n,m,q,a[N][N],b[N][N];//b数组是差分数组
 8 void insert(int x1,int y1,int x2,int y2,int c)//对差分数组的建立、操作
 9 {
10     b[x1][y1]+=c;
11     b[x2+1][y1]-=c;
12     b[x1][y2+1]-=c;
13     b[x2+1][y2+1]+=c;
14 }
15 int main()
16 {
17     ios_base;
18     cin>>n>>m>>q;
19     for (int i = 1; i <= n; i++)
20     {
21         for (int j = 1; j <= m; j++)
22         {
23             cin>>a[i][j];
24         }    
25     }
26     for (int i = 1; i <= n; i++)//开始建立差分数组
27     {
28         for (int j = 1; j <= m; j++)
29         {
30             insert(i,j,i,j,a[i][j]);
31         }    
32     }
33     while (q--)
34     {
35         int x1,y1,x2,y2,c;
36         cin>>x1>>y1>>x2>>y2>>c;
37         insert(x1,y1,x2,y2,c);//根据题意，在差分数组上进行插值的操作
38     }
39     for (int i = 1; i <= n; i++)//在差分数组b上直接进行操作：由差分数组复原回原数组
40     {
41         for (int j = 1; j <= m; j++)
42         {
43             b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
44         }    
45     }
46     for (int i = 1; i <= n; i++)
47     {
48         for (int j = 1; j <= m; j++)
49         {
50             cout<<b[i][j]<<' ';
51         }
52         cout<<'\n';
53     }
54     
55     return 0;
56 }