Skip to content

差分数组

一、解释🧀

对一个有 \(n\) 个元素的数组 \(a\) , 差分数组 \(b\) 的计算方法为：对任意 \(1≤i≤n\) ，都有\(b_i=a_i-a_{i-1}\) 。差分可以理解为前缀和的逆运算，对差分数组 \(b\) 进行前缀和操作之后，会得到原来的数组 \(a\) 。

在绝大多数情况下，我们对数组 \(a\) 的修改操作都是单点修改，即对数组的一个值进行修改，那么直接修改原数组的时间复杂度为 \(O(1)\) 。

  • 如果我们需要数组 \(a\) 中满足 \(p\leq i\leq q\) 的所有 \(a_i\) 都进行修改，那如果使用进行 \(q-p+1\) 次单点修改，时间复杂度为 \(O(n)\) 。如果进行 \(q\) 次修改，那么时间复杂度将达到 \(O(nq)\) 。

  • 如果我们对原数组作差分，就只需要对区间修改的两个端点进行修改即可，时间复杂度为 \(O(1)\) 。进行q次修改之后，再通过前缀和还原出原数组，时间复杂度就被优化为 \(O(n+q)\) 。

Tip

要对一个区间加上或者减去一个数，可以通过仅修改差分数组的两个端点来实现，而不遍历整个区间。

差分时间复杂度： \(O(1)\)

遍历数组时间复杂度：\(O(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
26
27
28
#include <bits/stdc++.h>
using namespace std;
int a[100] = {0, 1, 2, 3, 4, 5, 6, 7};
int b[100];
int main() {
    int n = 7;
    /*
    区间2-5都加3
    b[6]要先-3，再加3，最后是0
    */
    b[2] += 3, b[6] -= 3;
    for (int i = 0; i < n; i++) {
        b[i] += b[i - 1];
    }
    for (int i = 0; i < n; i++) {
        a[i] += b[i];
    }
    for (int i = 0; i < n; i++) {
        cout << a[i];
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << b[i];
    }
}
/*
用于快速修改大量数组，而不爆时间复杂度
*/
Example 
 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
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;
const int N = 100010;  // 根据题目范围修改

int a[N];     // 原数组
int d[N];     // 差分数组
int n;        // 数组长度

// 构建差分数组
void init() {
    d[0] = a[0];
    for(int i = 1; i < n; i++) {
        d[i] = a[i] - a[i-1];
    }
}

// 区间加操作
void add(int l, int r, int val) {
    d[l] += val;
    d[r + 1] -= val;
}

// 还原原数组
void get_origin() {
    a[0] = d[0];
    for(int i = 1; i < n; i++) {
        a[i] = a[i-1] + d[i];
    }
}

int main() {
    int m;  // 操作次数
    cin >> n >> m;
    // 读入原数组
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }    
    // 构建差分数组
    init();
    // 处理操作
    while(m--) {
        int l, r, val;
        cin >> l >> r >> val;
        l--;  // 转换为0基下标
        r--;
        add(l, r, val);
    }
    // 还原并输出结果
    get_origin();
    for(int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n-1];
    }

    return 0;
}

例题🧀

e.g.23 重新排序🧀

问题描述

给定一个数组 A 和一些查询 \(L_i,R_i\), 求数组中第 \(L_i\)至第 \(R_i\)个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?

输入格式

输入第一行包含一个整数 \(n\) 。

第二行包含 \(n\) 个整数\(A_1,A_2,⋯,A_n\), 相邻两个整数之间用一个空格分隔。

第三行包含一个整数\(m\)表示查询的数目。

接下来 \(m\)行, 每行包含两个整数 \(L_i、R_i\) 相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

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

样例输出

1
4

样例说明

原来的和为 \(6+14=20\), 重新排列为 \((1,4,5,2,3)\) 后和为 \(10+14=24\), 增加了 \(4\)。

评测用例规模与约定

对于所有评测用例, \(1≤n,m≤10^5,1≤A_i≤10^6,1≤L_i≤R_i≤10^6\)。

Tip

思路：让大的数字被查询的机会更多即可

 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, m, a[N], b[N];
int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        b[l] += 1;
        b[r + 1] -= 1;
    }
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1]; 
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << b[i] << " ";
    // }
    int ans1 = 0;
    for (int i = 0; i <= n; i++) {
        ans1 += a[i] * b[i];
    }
    sort(b + 1, b + n + 1);
    sort(a + 1, a + n + 1);
    int ans2 = 0;
    for (int i = 1; i <= n; i++) {
        ans2 += a[i] * b[i];
    }
    cout << ans2 - ans1;
}

e.g.24 [NewOJ Week 6] 推箱子🧀

题目描述

在一个高度为\(H\)的箱子前方，有一个长和高为\(N\)的障碍物。 障碍物的每一列存在一个连续的缺口，第i列的缺口从第l各单位到第h个单位（从底部由\(0\)开始数）。 现在请你清理出一条高度为\(H\)的通道，使得箱子可以直接推出去。 请输出最少需要清理的障碍物面积。 如下图为样例中的障碍物，长和高度均为\(5\)，箱子高度为\(2\)。（不需要考虑箱子会掉入某些坑中）

最少需要移除两个单位的障碍物可以造出一条高度为2的通道。

ECUST1819_P1.png

输入格式

输入第一行为两个正整数N和H，表示障碍物的尺寸和箱子的高度，\(1≤H≤N≤1000000\)。 接下来\(N\)行，每行包含两个整数\(l_i\)和\(h_i\)，表示第i列缺口的范围，\(0≤l_i≤h_i<N\)。

输出格式

输出一个数字表示答案。

输入样例 

1
2
3
4
5
6
5 2
2 3
1 2
2 3
1 2
2 3

输出样例 

1
2

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10; // 最大列数范围

ll n, h, a[N], s[N];

int main() {
    cin >> n >> h; // 输入列数和目标通道高度

    // 构建差分数组
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r; // 输入每列缺口范围
        l++, r++;      // 因为数组是从1开始索引
        a[l]++;        // 差分起点 +1
        a[r + 1]--;    // 差分终点 +1 的下一位 -1
    }

    // 差分数组前缀和，计算每一列的障碍物数量
    for (int i = 1; i <= n; i++) {
        a[i] += a[i - 1];
    }

    // 构建前缀和数组，快速查询任意区间的障碍物总数
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }

    ll ans = 1e18; // 初始化答案为一个极大值

    // 滑动窗口计算高度为 h 的通道需要清理的最小面积
    for (int i = h; i <= n; i++) {
        // 清理的面积 = 总高度 n*h - 当前通道内障碍物面积
        ans = min(ans, n * h - (s[i] - s[i - h]));
    }

    cout << ans << endl; // 输出结果
    return 0;
}

e.g.25 棋盘🧀

问题描述

小蓝拥有 \(n×n\) 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 \(m\)次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反（也就是白色棋子变为黑色，黑色棋子变为白色）。请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式

输入的第一行包含两个整数 \(n\)，\(m\)，用一个空格分隔，表示棋盘大小与操作数。

接下来\(m\) 行每行包含四个整数 \(x_1，y_1，x_2，y_2\)，相邻整数之间使用一个空格分隔，表示将在 \(x_1\) 至 \(x_2\) 行和\(y_1\) 至 \(y_2\) 列中的棋子颜色取反。

输出格式

输出 \(n\)行，每行 \(n\)个 \(0\)或 \(1\)表示该位置棋子的颜色。如果是白色则输出\(0\)，否则输出\(1\)。

样例输入

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

样例输出

1
2
3
001
010
100

评测用例规模与约定

对于所有评测用例，\(1≤n,m≤2000\)，\(1≤x_1≤x_2≤n\)，\(1≤y_1≤y_2≤m\)。

 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e3 + 10;
int n, m, a[N][N];

int32_t main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        a[x1][y1]++, a[x2 + 1][y2 + 1]++;
        a[x1][y2 + 1]--, a[x2 + 1][y1]--;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] % 2 == 1)
                cout << 1;
            else
                cout << 0;
        }
        cout << endl;
    }
}

注意到，反转棋子与将棋子的值异或 \(1\) 等效，可以采取区间异或的写法。

 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
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 2, vector<int>(n + 2));
    for (int i = 1; i <= m; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        a[x1][y1] ^= 1;
        a[x2 + 1][y1] ^= 1;
        a[x1][y2 + 1] ^= 1;
        a[x2 + 1][y2 + 1] ^= 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] ^= a[i - 1][j - 1] ^ a[i][j - 1] ^ a[i - 1][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << a[i][j];
        cout << endl;
    }
    return 0;
}

e.g.26 三体攻击🧀

题目描述

三体人将对地球发起攻击。为了抵御攻击，地球人派出了 \(A\times B\times C\) 艘战舰，在太空中排成一个 \(A\) 层 \(B\) 行 \(C\) 列的立方体。其中，第 \(i\) 层第 \(j\) 行第 \(k\) 列的战舰（记为战舰 \((i, j, k)\)）的生命值为 \(d(i, j, k)\)。

三体人将会对地球发起 \(m\) 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 \(t\) 轮攻击用 \(7\) 个参数 \(la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t\) 描述；

所有满足 \(i\in [la_t, ra_t],j\in [lb_t, rb_t],k\in [lc_t, rc_t]\) 的战舰 \((i, j, k)\) 会受到 \(h_t\) 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。

地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

输入格式

从标准输入读入数据。

第一行包括 \(4\) 个正整数 \(A\)，\(B\)，\(C\)，\(m\)；

第二行包含 \(A\times B\times C\) 个整数，其中第 \(((i − 1)\times B + (j − 1)) \times C + (k − 1)+1\) 个数为 \(d(i, j, k)\)；

第 \(3\) 到第 \(m + 2\) 行中，第 \((t + 2)\) 行包含 \(7\) 个正整数 \(la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t\)。

输出格式

输出到标准输出。

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

输入输出样例

输入 

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

输出 

1
2

说明/提示

【样例解释】

在第 \(2\) 轮攻击后，战舰 \((1,1,1)\) 总共受到了 \(2\) 点伤害，超出其防御力导致爆炸。

【数据约定】

对于 \(10\%\) 的数据，\(B = C = 1\)；

对于 \(20\%\) 的数据，\(C = 1\)；

对于 \(40\%\) 的数据，\(A\times B \times C, m\le10000\)；

对于 \(70\%\) 的数据，\(A, B, C \le 200\)；

对于所有数据，\(1\le A\times B\times C \le 10^6\)，\(1\le m \le 10^6\)，\(0 \le  (i, j, k)\), \(h_t\le 10^9\)。

假设 \(n\) 次攻击可以引爆某一艘战舰，那么大于 \(n\) 的攻击次数一定也能引爆该战舰。也就是说，答案是具备单调性的。考虑二分该答案，并通过三维差分快速计算 \(mid\) 次攻击次数时是否存在一个位置的生命值小于或等于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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vec vector

void cold_beans() {
    int a, b, c, m;
    cin >> a >> b >> c >> m;
    vec d(a + 1, vec(b + 1, vec<int>(c + 1)));
    vec<int> la(m + 1), ra(m + 1), lb(m + 1), rb(m + 1), lc(m + 1), rc(m + 1), h(m + 1);
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            for (int k = 1; k <= c; k++)
                cin >> d[i][j][k];
    for (int i = 1; i <= m; i++)
        cin >> la[i] >> ra[i] >> lb[i] >> rb[i] >> lc[i] >> rc[i] >> h[i];
    int l = 1, r = m, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        vec cf(a + 2, vec(b + 2, vec<int>(c + 2)));
        for (int i = 1; i <= mid; i++) {
            cf[la[i]][lb[i]][lc[i]] -= h[i];
            cf[ra[i] + 1][lb[i]][lc[i]] += h[i];
            cf[la[i]][rb[i] + 1][lc[i]] += h[i];
            cf[la[i]][lb[i]][rc[i] + 1] += h[i];
            cf[la[i]][rb[i] + 1][rc[i] + 1] -= h[i];
            cf[ra[i] + 1][lb[i]][rc[i] + 1] -= h[i];
            cf[ra[i] + 1][rb[i] + 1][lc[i]] -= h[i];
            cf[ra[i] + 1][rb[i] + 1][rc[i] + 1] += h[i];
        }
        for (int i = 1; i <= a; i++)
            for (int j = 1; j <= b; j++)
                for (int k = 1; k <= c; k++)
                    cf[i][j][k] = cf[i][j][k] + cf[i - 1][j][k] + cf[i][j - 1][k] + cf[i][j][k - 1] - cf[i - 1][j - 1][k] - cf[i - 1][j][k - 1] - cf[i][j - 1][k - 1] + cf[i - 1][j - 1][k - 1];
        // for (int i = 1; i <= a; i++)
        //     for (int j = 1; j <= b; j++)
        //         for (int k = 1; k <= c; k++)
        //             cerr << cf[i][j][k] << ' ';
        // cerr << endl;
        bool flag = 0;
        for (int i = 1; i <= a; i++)
            for (int j = 1; j <= b; j++)
                for (int k = 1; k <= c; k++)
                    if (d[i][j][k] + cf[i][j][k] < 0)
                        flag = 1;
        if (flag) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--)
        cold_beans();
    return 0;
}