前綴和把「區間求和」從 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)：
目標 = 全部 - 上面 - 左邊 + 左上角（被減兩次所以加回來）
sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
容斥原理。面試手畫一下圖就很清楚，不用死背公式。
差分陣列
前綴和的逆運算。用於「O(1) 區間加值」：
要對 [1,3] 加 2：
diff[1] += 2
diff[4] -= 2 (如果 4 < n)
然後做前綴和還原出結果
diff[left] += val;
if (right + 1 < n) diff[right + 1] -= val;
// 還原
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 技巧你懂了，這題就只是把它套在前綴和上。
前綴和就像你的銀行帳戶餘額：你不需要把每筆交易重新加一遍，看一眼餘額就知道總共多少。差分陣列則是你的交易明細——記錄「變化量」而不是「絕對值」。