算法中的『前缀和』及『差分』思想详解_差分思想

一、基本原理以及实现

1. 一维前缀和

• 一维前缀和的定义：对于一个从下标从『1』开始的长度为『$n$』的一维数组 『$a_1,a_2,a_3,...,a_n$』，前缀和的计算公式为『$S_i=a_1+a_2+...+a_i$』。
  • 如何求解『$S_i$』：

    S[0] = 0;
    for (int i = 1; i <= n; ++i) {
       S[i] = S[i - 1] + a[i];
    }
    1
    2
    3
    4

  • 作用：快速的求解原数组中任意一段 [l,r] 的和『$S=S_r-S_{l-1}$』，计算的时间复杂度为$O(1)$。
  • 为什么原数组下标必须从1开始：定义『$S_0=0$』可以更好地处理边界问题，统一公式为『$S=S_r-S_{l-1}$』。例如计算『$S_{10}$』也可以写成『$S_{10}=S_{10}-S_0$』。

2. 二维前缀和

• 二维前缀和的定义：对于一个从下标从『1』开始的大小为『$n\times m$』的二维数组 『$a_{ij}$』，前缀和的计算公式为『$S_{ij}=a_{11}+a_{12}+...+a_{1j}+a_{21}+a_{22}+...+a_{2j}+...+a_{i1}+a_{i2}+...+a_{ij}$』，即为其左上角所有元素的和。
  • 如何求解『$S_{ij}$』：

    S[0][0] = 0; S[0][1] = 0; S[1][0] = 0;
    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] + a[i][j];
    }
    1
    2
    3
    4
    5

  • 作用：快速的求解原二维数组中任意一块矩形 $[l_1$ ~ $l_2,r_1$ ~ $r_2]$ （$l_2>l_1,r_2>r_1$）的和『$S=S_{l_2{r}_2}-S_{(l_1-1)r_2}-S_{l_2(r_1-1)}+S_{(l_1-1)(r_1-1)}$』，计算的时间复杂度为$O(1)$。

3. 一维差分

• 一维差分的定义：对于一个从下标从『1』开始的长度为『$n$』的一维数组 『$a_1,a_2,a_3,...,a_n$』，构造一个新数组『$b_1,b_2,b_3,...,b_n$』，使得『$a_i$』是『$b$』数组的前缀和，即『$a_i=b_1+b_2+...+b_i$』，此时『$b$』数组称为『$a$』数组的差分。
  • 如何构造『$b_i$』数组：『$b_1=a_1,b_2=a_2-a_1,b_3=a_3-a_2,...,b_n=a_n-a_{n-1}$』
  • 作用：快速的求解原数组经过一系列操作后得到的新数组，操作具体为在原数组中任意一段 [l,r] 区间内的所有数加上一个常数『$c$』。这一系列操作利用差分的思想可以直接对『$b$』数组进行时间复杂度为$O(1)$的计算即可，具体计算方法是『$b_l+c;b_{r+1}-c$』。此时『$b_i$』数组的前缀和即为操作后的结果。

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

  • 『$b_l+c;b_{r+1}-c$』理解：
    • 『$b_l+c$』使得『$a_1^{\ast }=a_1,a_2^{\ast }=a_2,...,a_l^{\ast }=a_l+c,a_{l+1}^{\ast }=a_{l+1}+c,...,a_r^{\ast }=a_r+c,a_{r+1}^{\ast }=a_{r+1}+c,...,a_n^{\ast }=a_n+c$』；
    • 然后，『$b_{r+1}-c$』使得『$a_1^{\ast }=a_1,a_2^{\ast }=a_2,...,a_l^{\ast }=a_l+c,a_{l+1}^{\ast }=a_{l+1}+c,...,a_r^{\ast }=a_r+c,a_{r+1}^{\ast }=a_{r+1},a_{r+2}^{\ast }=a_{r+2},...,a_n^{\ast }=a_n$』，即完成了操作要求。
  • 注意：给定了『$a_1,a_2,a_3,...,a_n$』数组，我们其实可以看做是一个全『$0$』数组进行一系列操作后得到的『$a$』数组，此处的一系列操作为『$[1,1]+a_1,[2,2]+a_2,...,[n,n]+a_n$』。因此可以假定初始数组为全『$0$』数组，显然『$b$』数组也为全『$0$』数组，因此『$b$』数组的构造不是很重要。

4. 二维差分

• 二维差分的定义：对于一个从下标从『1』开始的长度为『$n\times m$』的二维数组 『$a_{ij}$』，构造一个新数组『$bij$』，使得『$a_{ij}$』是『$b_{ij}$』的前缀和，此时『$b$』数组称为『$a$』数组的差分。
  • 如何构造『$b_{ij}$』数组：参考一维差分，我们可以假定初始二维数组为全『$0$』数组，显然『$b$』数组也为全『$0$』二维数组。
  • 作用：快速的求解原二维数组经过一系列操作后得到的新二维数组，操作具体为在原二维数组中任意一个子矩阵内的所有数加上一个常数『$c$』。这一系列操作利用差分的思想可以直接对『$b_{ij}$』数组进行时间复杂度为$O(1)$的计算即可，具体计算方法是『$b_{l_1{r}_1}+c;b_{(l_2+1)r_1}-c;b_{l_1(r_2+1)}-c;b_{(l_2+1)(r_2+1)}+c;$』。此时『$b_{ij}$』数组的前缀和即为操作后的结果。

  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;
  }
  1
  2
  3
  4
  5
  6

二、应用：模板题

（一维前缀和）AcWing 795. 前缀和

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

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 ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化

    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（二维前缀和）AcWing 796. 子矩阵的和

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N], a[N][N];;

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]);

    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] + a[i][j]; // 求前缀和

    while (q -- ) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); // 求子矩阵的和
    }

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

（一维差分）AcWing 797. 差分

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

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]);  // 这里由于假定初始数组全 0，因此需要先进行预操作

	 // 这里是题目要求的 m 次操作
    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];  // 求解操作完后 b 数组的前缀和即为答案

    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

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

（二维差分）AcWing 798. 差分矩阵

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
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]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);  // 这里由于假定初始数组全 0，因此需要先进行预操作

    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];  // 求解操作完后 b 数组的前缀和即为答案

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}
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
38
39
40
41
42
43
44