差分往往伴随前缀和
https://www.acwing.com/problem/content/800/
求矩阵的->
1. 前缀和
a b
c d
若要用前缀和求上面元素的和
d + s[b] + s[c] - s[a] (s表示前缀和)
2. 差分
a b c
d e f
h i j
若要让上面这部分矩阵每个元素➕2
+2..0..0.-2
..0..0..0
..0..0..0
-2.........+2
code
#include<iostream>
using namespace std;
const int N = 1010;
int n, m, q;
//1 差分数组s
int g[N][N], s[N][N];
int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> g[i][j];
}
}
while(q --){
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
//2 计算差分数组
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
//3 差分数组的前缀和
s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
cout << g[i][j] + s[i][j];
if(j != m) cout << " ";
else cout << endl;
}
}
return 0;
}