算法 - 前缀和与差分

2020-08-05 09:10:32

前缀和唯一作用就是对一段区间方便求和。差分是前缀和的逆运算

前缀和

一维数组前缀和：

规定： s[i] = a[1] + a[2] + a[3] ... + a[i]

所以， 方便求和 a[i] ~ a[j] :

s[j] = a[1] + a[2] + a[3] ... + a[i - 1] + a[i] + ... + a[j]

s[i - 1] = a[1] + a[2] + a[3] ... + a[i - 1]

所以 s[j] - s[i - 1] = $\sum_{i}^j a[i]$

c++ 模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int N = 1010;
int q[N], s[N];

int main() {
   // 存放的时候一定注意是从1开始存放，这样前缀和 i - 1 就不会越界
   for(int i = 1; i <= n; i++) cin >> q[i];

   // 求前缀和
   for(int i = 1; i <= n; i++) s[i] = s[i - 1] + q[i];

   // 输出 i ~ j 的累加和
   cout << s[j] - s[i - 1] << endl;
   return 0;
}

二维数组前缀和：

这样一个二维数组，求蓝色部分的前缀和。

求蓝色区域的面积。可以分别为两个部分的前缀和，一个是x轴方向的前缀和，一个是y方向的前缀和。

s[i][j] 表示i * j 的整个数组的分别，比如 3 * 3 表示就是蓝色方框的数值。

所以s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

这里减去s[i - 1][j - 1] 是因为s[i - 1][j] 和 s[i][j - 1]都包含s[i - 1][j - 1]这个部分。

所以蓝色部分的用s[i][j] 表示可以用x1, y1, x2, y2表示为：

蓝色部分的面积 = s[x2][y2] = s[x1 - 1][y2] + s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

所以c++ 代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;
const int N = 1e5 + 5;
int s[N][N];
int n, m;

int main(0 {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> s[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];

    cin >> x1 >> y1 >> x2 >> y2;
    cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;
    return 0;
}

差分

差分运算是前缀和的逆运算。

有一个数组 a[N]， 构造一个辅助数组b[N]，

使得满足两个性质：

  1. a[i] = b[1] + b[2] + b[3] + ... + b[i]
  2. b[i] = a[i] - a[i - 1]

唯一一个应用就是在区间 [l, r] 区间内都加上 $c$。可以做到$O(1)$的复杂度。

  • 因为a[i]是b[1 ~ i]的前缀和。
  • 在b[l] + c， 在 b[r + 1] - c,再求前缀和。

在利用b[i]数组求a[i]的时候，在b[l] + c那么l之后的数据都会 + c，但是只要l ~ r区间 + c，所以在 r + 1的位置 - c就行了。

此外需要注意的是，在初始化b数组的时候，那么那么可以理解为b[1 ~ i] 都是0 然后在l ~ l的区间插入数据就可以了。

c++ 代码实现：

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

#include <iostream>

using namespace std;
const int N = 1010;
int a[N], b[N];
int n, m;

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


int main() {
    cin >> n >> m;
    // 读入a数组
    for(int i = 1; i <= n; i++) cin >> a[i];

    // 构造b数组
    for(int i = 1; i <= n; i++) insert(i, i, a[i]);

    // 进行m次数的插入操作
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    // 最终的数组, 利用前缀和进行构造
    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;
}

二维矩阵的差分运算：

所以插入操作就是：

b[x1][y1] += c
b[x1][y2 + 1] -= c
b[x2 + 1][y1] -= c
b[x2 + 1][y2 + 1] += c

接下来就是求前缀和。

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
45
46
47

#include <iostream>

using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
int 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;
    // 读取数组a
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    // 构造数组b
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; 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];

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


    return 0;
}
  1. 1. 前缀和
  2. 2. 差分