Loading... ### 定义 差分数组：定义 `b[1, i]`的前缀和等于 `a[i]` 二维差分数组同理 ### 构造差分 ```cpp // 一维 a[l] += c a[r + 1] -= c; // 二维 a[x1][y1] += c; a[x1][y2 + 1] -= c; a[x2 + 1][y1] -= c; a[x2 + 1][y2 + 1] += c; // 二维差分矩阵复原(与前缀和类似) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; ``` ### 模板 ### 一维差分 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100005; int n, m; int a[N], b[N]; void add(int x, int l, int r){ b[l] += x; b[r + 1] -= x; } int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(a[i], i, i); } int l, r, x; while (m--) { scanf("%d%d%d", &l, &r, &x); add(x, l, r); } for (int i = 1; i <= n; i++) b[i] += b[i - 1]; for (int i = 1; i <= n; i++) printf("%d ", b[i]); return 0; } ``` #### 二维差分矩阵 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N][N], b[N][N]; int n, m, q; void add(int x1, int y1, int x2, int y2, int x){ b[x1][y1] += x; b[x1][y2 + 1] -= x; b[x2 + 1][y1] -= x; b[x2 + 1][y2 + 1] += x; } int main(){ scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){ scanf("%d", &a[i][j]); add(i, j, i, j, a[i][j]); } int x1, y1, x2, y2, x; while (q--) { scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &x); add(x1, y1, x2, y2, x); } for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; cout << b[i][j] << " "; } cout << endl; } return 0; } ``` Last modification：February 14, 2023 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed