请写一个二维差分的代码
时间: 2024-03-21 16:42:41 浏览: 15
二维差分(Two-dimensional Difference)是一种常用的算法,用于快速维护二维区域内的数值变化。下面是一个简单的二维差分的 C++ 代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int n, m;
int a[N][N], d[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
d[x1][y1] += c;
d[x2 + 1][y1] -= c;
d[x1][y2 + 1] -= c;
d[x2 + 1][y2 + 1] += c;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
insert(i, j, i, j, a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
cout << d[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
该代码使用 `d` 数组维护二维差分。在输入时,对于每个元素 `(i, j)`,将其插入到差分数组中,即将 `(i, j)` 的值加到 `(i, j)` 和 `(i+1, j+1)` 的位置上,并将其从 `(i+1, j)` 和 `(i, j+1)` 的位置上减去。最后,使用前缀和计算差分数组,以获得原始数组的每个元素。