一维差分

所谓差分其实就是前缀和的逆运算！已知存在数列：$a_1,a_2,a_3,a_4,a_5...a_{n-1},a_n$。我们构造一个它的差分数列：$b_1,b_2,b_3,b_4...b_{n-1},b_n$ 使得数列 $b$ 的前缀和 $s$ 是数列 $a$。此时数列 $b$ 就是数列 $a$ 的差分。

引例

问题描述：

输入一个长度为 $n$ 的整数序列。 接下来输入 $m$ 个操作，每个操作包含三个整数 $l、r、c$，表示将序列中 $l、r$ 之间的每个数加上 $c$。 请你输出进行完所有操作后的序列。

当我们在数列 $a$ 的 $l$ 到 $r$ 之间每个数都加上 $c$ 时，对于数列 $b$ 只需要让它 $b_l+c$ 且 $b_{r+1}-c$ 即可，这样对 $b$ 求前缀和后得到的数列 $a$ 在 $l$ 到 $r$ 之间的每个数就都加上 $c$ 了。

那么我们如何构造初始的数列 $b$ 呢？我们可以假设初始时数列 $a$ 和数列 $b$ 都是全为 $0$（它满足差分性质），对于每一个元素 $a_i$ 它其实就是在 $i$ 到 $i$ 的位置上插入 $a_i$ 而已，这样自然而言数列 $b$ 就构造出来了。

#include <iostream>
using namespace std;

int const N = 1e6 + 10;
int n,m, a[N], b[N];

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

int main() {
    cin >> n >> m;
    // 读入a 构造b
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        insert(i, i, a[i]);
    }

	// m个询问
    while(m --) {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

	// 对b求前缀和，结果即是更新后的a数组
    for(int i = 1; i <= n; i++) {
        b[i] += b[i - 1];    // 这里我们为了节省空间直接修改了b数组，大家也可以开sum数组用原始方法求前缀和
        cout << b[i] << " ";
    }

    return 0;
}

二维差分

模板例题

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个操作，每个操作包含五个整数 $x_1,y_1,x_2,y_2,c$，其中 $(x_1,y_1)$ 和 $(x_2,y_2)$ 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 $c$。请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 $n,m,q$。接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。接下来 $q$ 行，每行包含 $5$ 个整数 $x_1,y_1,x_2,y_2,c$，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

样例输入

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

样例输出

2 3 4 1
4 3 4 1
2 2 2 2

参考代码

#include <iostream>
using namespace std;

int const N = 1010;
int a[N][N], b[N][N], n, m, q;

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    cin >> n >> m >> q;
    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]);
        }
    }

    while(q --) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    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;
}