c++标准做法
差分坑点简记
这里有个坑,差分要方便的话,要n+2.以(1, 2, 3, 4)为例,简单画图如下(2*2的原数据,需要用到4*4的存储空间):
为了方便反算回原数组,左边和上边要空出个0,这样反算的时候就可以简便处理。
这里比较难理解的是n+2右边和下边,是因为insert的时候,会超掉(超的其实是没有用到的,也可以省掉那点内存,但是代码要麻烦一点,要判x2 + 1 <= m + 1的时候才更新,否则一直segment fault)
代码
#include <iostream>
#include <vector>
using namespace std;
void sinsert(vector<vector<int>>& s, int x1, int y1, int x2, int y2, int c) {
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
int main(){
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> s(n + 2, vector<int>(m + 2));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int t;
cin >> t;
sinsert(s, i, j, i, j, t);
}
}
while (q--) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
sinsert(s, x1, y1, x2, y2, c);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cout << s[i][j] << " ";
}
cout << endl;
}
return 0;
}