簡介#
差分也是一種常見的小技巧，通常會用來處理一些區間的操作，例如區間修改等等。
差分的基本思想是在一個陣列中，對於區間 \([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 年的第三題 線段覆蓋長度！不過區間的定義跟這裡有點不一樣，需要稍微調整一下才能通過。
