[差分+模板] 差分模板

69 阅读 0 评论 46 点赞

我是靠谱客的博主老迟到秋天，这篇文章主要介绍[差分+模板] 差分模板，现在分享给大家，希望可以做个参考。

文章目录

- 0. 前言
- 1. 一维差分
- 2. 二维差分

0. 前言

对数组某个区间内都加、减一个值的话，差分数组可以达到 $O (1)$ 的时间完成这个操作。

预处理得到的差分数组的前缀和是原数组。对原数组 $[l, r]$ 区间加上 $c$ ，则仅需对差分数组的 $a [l] + c$ ， $a [r + 1] - c$ 即可。

最后再求一遍前缀和即可。

差分数组的定义为：差分数组的前缀和是原数组，那么怎么构造一个差分数组呢？其实我们并不需要想太多。

显然，全 0 数组作为差分数组时，它的前缀和数组也是全 0 的数组。

我们仅需遍历一遍输入的数组元素，在一个单位长度下，即 $[i, i] + c$ ，调用差分函数，将其插到全 0 数组的对应下标位置，就完成了对差分数组的初始化。

所以构造差分数组不重要，差分的过程，只有一个插入操作。

同理二维差分数组的初始化也是这样。

1. 一维差分

Biu

主要思想：

复制代码

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

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 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
#include <iostream>

using namespace std;

const int N = 1e5+5;

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() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    for (int i = 1; i <= n; ++i) insert(i, i, a[i]);
    
    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) cout << b[i] <<' ';
    
    return 0;
}

2. 二维差分

Biu

简单画下图很容易理解：

复制代码

1
2
3
4
5
6
7
8
9
10
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y2 + 1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
}

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[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
#include <iostream>

using namespace std;

const int N = 1e3+5;

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][y2 + 1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][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];
    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)
            cout << b[i][j] <<' ';
        cout << endl;
    }
    return 0;
    
}