前一篇：【演算法新手村】[初階]筆記05 - 前綴和(二維)

前面兩篇都是前綴和，這篇來講講跟前面兩組性質是有點像(都是在討論怎麼優化對數組的某個大量操作)，也是個概念很簡單的優化思想。

這邊引入一個問題，我要反覆對一個陣列的某一個部分進行加減法操作，我要知道最後的陣列長甚麼樣子。

給定一個長度為 N 的陣列，現在有 Q 次操作，每次操作要求將區間 [L, R] 內的所有數字全部加上 k。最後請輸出修改完成後的陣列。

暴力解

最直覺的寫法：每次操作都跑一個 for 迴圈從 L 加到 R。

for(int i = L ; i <= R ; i++){
	A[i] += k;
}

最糟情況下，也就是每次都對整個陣列進行操作，會需要做N×Q次的加法(時間複雜度同樣是 O(Q×N))。當 N、Q較大時就會 TLE ( ex : N,Q = 10⁵ )。

差分法

首先，我們先建立差分陣列 D[i]，其定義為：D[i] = A[i] - A[i-1]（當前項與前一項的差）。

它前綴和的關係非常奇妙，如果有數學直覺強的人已經看出來了，差分陣列的前綴和就是原陣列，即：A[i] = D[1] + D[2] + ... + D[i]。

如果我們要對區間 [L, R] 增加 k：

1. D[L] += k：這會讓我們在還原時，在 A 的 [L,N-1]都加上 k (從第 L 項開始的每一項都會多出 k )。
   但是我們只想要 [L,R] 的範圍而已怎麼辦?我們可以再多做一步。
2. D[R+1] -= k：在 A 的 [R+1,N-1]都減掉 k (這會抵消掉剛才多的 k)，最終從第 R+1 項開始的還原值回到原本的狀態。需要注意的是索引R+1有可能越界，要進行檢查。

這樣我們只需要改動兩個點，就能代表整個區間的變化！

程式碼實作 (C++)

同樣建議使用索引 1 開始。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    
    vector<long long> a(n + 2, 0); // 原陣列
    vector<long long> d(n + 2, 0); // 差分陣列

    // 1. 讀取原陣列並建立差分
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }

    // 2. 進行 Q 次區間修改
    while (q--) {
        int L, R, k;
        cin >> L >> R >> k;
        d[L] += k;     // 起點增加 k
        if(R + 1 < n)
	        d[R + 1] -= k; // 終點的下一項扣掉 k
    }

    // 3. 還原陣列 (對差分陣列求前綴和)
    long long current_val = 0;
    for (int i = 1; i <= n; i++) {
        current_val += d[i];
        cout << current_val << " ";
    }
    cout << endl;

    return 0;
}

每次修改只需做兩次加減(時間複雜度O(1))(做Q次)，最後花 O(N) 還原陣列。總複雜度 O(Q + N)。

比較

假設陣列長度 N = 10⁵，修改次數 Q = 10⁵：

從上表不難得出，當你需要頻繁對一個範圍進行加減，且只需要在所有操作結束後知道最終結果時，差分是可以幫你節省很多不必要的運算。

總結

前綴和 主要是用在原始 陣列不會被改變 的情況下，反覆去求一個區間的和
而這篇的 差分 則是用在 頻繁對陣列的區間進行加減運算

差分可以理解為 前綴和的逆運算

• 前綴和：先把答案累加起來，查的時候用減法。
• 差分：先執行差值運算，最後用加法還原。

練習

1.LeetCode 1109. Corporate Flight Bookings

LeetCode 1109. Corporate Flight Bookings 詳解

2.LeetCode 1094. Car Pooling

(不讓我放連結，說是廣告...)

後面還有一篇二維差分的筆記，這個主題就要完成了，順帶一提，前綴和很常跟哈希表一起出現，之後我會補一些題目上去，寫這些筆記真的有長腦子的感覺OwO，可以感覺得出來之前學得不太扎實。