差分

簡介

差分也是一種常見的小技巧，通常會用來處理一些區間的操作，例如區間修改等等。

差分的基本思想是在一個陣列中，對於區間 $[l, r]$ 進行修改時，只需要對 $a[l]$ 和 $a[r+1]$ 分別作相反的修改。這樣，當我們需要查詢某個位置的值時，將差分序列的前綴和求出來即可。

這樣講起來可能有點抽象，我們來看一個例題。

例題

給定一維座標上一些區間，求出這些區間的交集的長度。

區間座標的範圍是 $[1, 10^5]$，每個區間的左右端點都是整數，且區間數量 $n$ 滿足 $1 \leq n \leq 10^5$。

比如說這張圖上的範例答案就是 $10$，因為只有 $[2, 3]$ 的地方沒有被覆蓋到。

這個問題可以用差分來解決，第一個步驟就是對於每個區間 $[l, r]$，對 $a[l]$ 打一個 $+1$ 的標記，對 $a[r+1]$ 打一個 $-1$ 的標記。

接下來只需要對差分序列求前綴和，就可以得到每個位置是否被覆蓋到。

假設目前掃到紫色這條線的位置，那目前的前綴和就是 $1$，表示這個位置被覆蓋到。

繼續掃過去就會再被 $-1$ 減掉，所以目前的前綴和是 $0$，表示這個位置沒有被覆蓋到。

知道這個原理之後，要寫程式就很簡單了。

// 讀入區間
for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    a[l]++;
    a[r + 1]--;
}
// 求差分前綴和
int cur = 0;
int ans = 0;
for (int i = 1; i <= 100; i++) {
    cur += a[i];
    // 如果 cur > 0，表示這個位置被覆蓋到
    if (cur > 0) {
        ans++;
    }
}
cout << ans << endl;

進階題

想像一下，如果這個問題的區間座標範圍是 $[1, 10^9]$，那這個問題就無法直接用上面的方法解決了。

如果要解決這個問題的話，首先我們要先觀察到一個性質：對於沒有遇到區間左端點或右端點的位置，前綴和是不會變化的。也就是說，其實很多陣列的空間都被浪費掉了。我們只需要在乎區間的左右端點就好，不用真的開一個 $10^9$ 大小的陣列。

實作上，我們要記錄這段交集區間的左端點，然後在遇到右端點時，計算這段區間的長度。

// 讀入區間
vector<pair<int, int>> pos;
for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    pos.push_back({l, 1});
    pos.push_back({r + 1, -1});
}
// 排序
sort(pos.begin(), pos.end());
// 求差分前綴和
int cur = 0;
int ans = 0;
int last = 0;
for (int i = 0; i < pos.size(); i++) {
    cur += pos[i].second;
    // 記錄這段交集區間的左端點
    if (pos[i].second == 1 && cur == 1) {
        last = pos[i].first;
    }
    // 遇到右端點時計算這段區間的長度
    if (pos[i].second == -1 && cur == 0) {
        ans += pos[i].first - last - 1;
    }
}
cout << ans << endl;

這題其實就是 APCS 2016 年的第三題 線段覆蓋長度！不過區間的定義跟這裡有點不一樣，需要稍微調整一下才能通過。