前綴和把「區間求和」從 O(n) 降到 O(1)。差分陣列把「區間更新」從 O(n) 降到 O(1)。兩個互為逆運算，一起學最有效率。
查詢用前綴和，更新用差分
| 前綴和 | 差分陣列 | |
|---|---|---|
| 預處理 | O(n) | O(n) |
| 區間查詢 | O(1) | 需還原 O(n) |
| 區間更新 | O(n) | O(1) |
| 適用 | 多次查詢 | 多次更新 |
多次查詢用前綴和，多次更新用差分。搞反了就是把 O(1) 用成 O(n)。
前綴和
原始陣列: [1, 2, 3, 4, 5]
前綴和: [0, 1, 3, 6, 10, 15]
↑ 哨兵（很重要！）
區間和 [1,3] = prefix[4] - prefix[1] = 10 - 1 = 9 → (2+3+4)long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++)
prefix[i + 1] = prefix[i] + nums[i];
// 查詢 [left, right]
long sum = prefix[right + 1] - prefix[left];那個 prefix[0] = 0 的哨兵很關鍵。沒有它，查詢 [0, right] 就需要特殊處理。加了哨兵，公式統一。
二維前綴和
矩陣: 前綴和:
1 2 3 0 0 0 0
4 5 6 0 1 3 6
7 8 9 0 5 12 21
0 12 27 45查詢子矩陣 (r1,c1) 到 (r2,c2)：
┌─────┬───────────────┐
│ A │ B │
├─────┼───────────────┤
│ C │ 目標區域 │
└─────┴───────────────┘
目標 = 全部 -（上面 B）-（左邊 C）+（左上角 A，被扣兩次所以加回來）
sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]容斥原理。左上角那塊 A 在減 B 和減 C 時各被扣了一次，所以要補回來——面試手畫一下這張圖就很清楚，不用死背公式。
差分陣列
前綴和的逆運算。用於「O(1) 區間加值」：
要對 [1,3] 加 2：
diff[1] += 2
diff[4] -= 2 (如果 4 < n)
然後做前綴和還原出結果diff[left] += val;
if (right + 1 < n) diff[right + 1] -= val;
// 還原
result[0] = diff[0]; // 別漏這行：從 index 0 開始的區間更新全靠它
for (int i = 1; i < n; i++)
result[i] = result[i-1] + diff[i];實際場景：航班預訂（LeetCode 1109）、拼車（LeetCode 1094）——大量的區間更新操作，一個一個改太慢，差分陣列一次 O(1) 搞定。
前綴和 + HashMap：最常考的進階技巧
「和為 K 的子陣列個數」——暴力 O(n²)，前綴和 + HashMap O(n)。
核心洞見：如果 prefix[j] - prefix[i] == k，那 [i, j) 的子陣列和就是 k。所以只要看之前有沒有出現過 prefix[j] - k。
int subarraySum(int[] nums, int k) {
Map<Long, Integer> map = new HashMap<>();
map.put(0L, 1); // 前綴和為 0 出現 1 次
long sum = 0;
int count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.merge(sum, 1, Integer::sum);
}
return count;
}這個「前綴和 + HashMap」的組合在面試裡出現的頻率超高。Two Sum 的 HashMap 技巧你懂了，這題就只是把它套在前綴和上。
🎬 互動視覺化：前綴和區間查詢 — 拖動左右邊界，即時看「尾端累計減開頭累計」怎麼一步湊出區間和。
前綴和就像你的銀行帳戶餘額：你不需要把每筆交易重新加一遍，看一眼餘額就知道總共多少。差分陣列則是你的交易明細——記錄「變化量」而不是「絕對值」。
接下來往哪走
- Math Algorithms 數學演算法 — 下一篇：GCD、質數篩、快速冪，演算法技巧篇的最後一站
- Fenwick Tree (BIT) 樹狀陣列 — 前綴和的痛點是「資料會改」——樹狀陣列讓更新和查詢都是 O(log n)
- Rolling Hash 滾動雜湊：O(1) 的子字串比較 — 把「前綴相減」的思想從數字搬到字串雜湊上