一维差分

差分是前缀和的逆运算，差分数组的作用是在 O(1) 的时间复杂度内，对原数组中某一段区间 [l, r] 内的所有数加上一个固定的值。

给定数组 a1,a2,...,ana_1, a_2, ... , a_n（前缀和）

构造 b1,b2,...,bnb_1, b_2, ... , b_n（差分）

使得 ai=b1+b2+...+bia_i = b_1 + b_2 + ... + b_i

构造方式
b1=a1b_1 = a_1
b2=a2−a1b_2 = a_2 - a_1
b3=a3−a2b_3 = a_3 - a_2
…
bn=an−an−1b_n = a_n - a_{n-1}

可以在 O(n)O(n) 的时间复杂度内由 {bn}\{b_n\} 得到 {an}\{a_n\}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

const int N = 100010;

int n, m;
int a[N]={0}, b[N]={0};

void insert(int l, int r, int c) {
    b[l]+=c;
    b[r+1]-=c;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=1;i<=n;i++) insert(i, i, a[i]);
    while(m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1]; // 计算 a[i]
    for(int i=1;i<=n;i++) printf("%d ", b[i]);
    return 0;
}

二维差分

原矩阵 {aij}\{a_{ij}\}
构造差分矩阵 {bij}\{b_{ij}\}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

int n, m, q;

const int N = 1010;

int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
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]);
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--) {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&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];
            printf("%d ", b[i][j]);
        }
        puts("");
    }
    return 0;
}