差分与前缀和

差分是前缀和的逆运算：对差分数组求一遍前缀和，就还原回原数组。它最大的用处是把「区间加」的修改从 O(n) 变成 O(1)——只需要在两端打上标记。

一维差分：P3406 海底高铁

P3406 海底高铁 - 洛谷

题目要翻译一下：乘客按顺序经过若干段铁路，每一段可以「买票」也可以「买 IC 卡」。判断每一段到底买什么更划算，就是简单贪心；而「每一段被经过多少次」用差分统计。

易错点：处理 diff 左右端点时，右端点不需要 r++。因为我们要的是区间被覆盖的次数，diff[start]++、diff[end]-- 即可。

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<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Pay { ll a, b, c; };

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> p(m + 1);
    for (int i = 1; i <= m; i++) cin >> p[i];

    vector<Pay> pay(n);
    for (int i = 1; i < n; i++) cin >> pay[i].a >> pay[i].b >> pay[i].c;

    vector<int> diff(n + 2, 0);
    for (int i = 1; i < m; i++) {
        int start = min(p[i], p[i + 1]);
        int end   = max(p[i], p[i + 1]);
        diff[start]++;
        diff[end]--;               // 右端点不用 +1，覆盖次数到 end-1 为止
    }

    for (int i = 1; i < n; i++) diff[i] += diff[i - 1];

    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ll times   = diff[i];
        ll buyCard = pay[i].c + times * pay[i].b;
        ll buyTicket = pay[i].a * times;
        ans += min(buyCard, buyTicket);
    }
    cout << ans << endl;
    return 0;
}

二维差分：P3397 地毯

P3397 地毯 - 洛谷

算是模板题，没有弯弯绕绕。每次把一块矩形区域全部 +1，最后前缀和还原。

易错点：右下角 (x2+1, y2+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;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    vector<vector<int>> diff(n + 2, vector<int>(n + 2, 0));

    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        diff[x1][y1]++;
        diff[x1][y2 + 1]--;
        diff[x2 + 1][y1]--;
        diff[x2 + 1][y2 + 1]++;    // 被减掉两次，加回来一次
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            cout << diff[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

总结

  • 一维差分：统计区间覆盖次数 / 区间加，diff[l]++、diff[r]--，再前缀和还原。
  • 二维差分：矩形区域加，四个角打标记，再二维前缀和还原。
  • 差分常和贪心搭配（如 P3406），也要注意端点到底开不开这种细节。