前綴和與差分陣列 Prefix sums and difference arrays · 演算法 Algorithms

前綴和與差分陣列

先花 O(n) 算好前綴和，之後任何區間的總和都只要一次減法；反過來，差分陣列讓「整段都加上一個數」也只要改兩格。

做什麼

從3

到8

1/13

9
0
3
1
2
2
1
3
3
4
5
5
1
6
9
7
6
8
7
9
7
10
4
11

prefix（比 a 多一格）

正在計算答案讀寫的格子區間

prefix[1] = prefix[0] + a[0] = 0 + 9 = 9：位置 1 之前所有數的總和。只建一次，一趟就完成。

亮起來的是這一步執行的程式碼

1function buildPrefix(a: number[]): number[] {
2  const prefix = [0];
3  for (const x of a) prefix.push(prefix[prefix.length - 1] + x);
4  return prefix;
5}
6 
7function rangeSum(prefix: number[], l: number, r: number): number {
8  return prefix[r + 1] - prefix[l];
9}
10 
11function applyRangeAdds(a: number[], updates: [number, number, number][]): number[] {
12  const diff = new Array(a.length + 1).fill(0);
13  for (let i = 0; i < a.length; i++) {
14    diff[i] = a[i] - (i > 0 ? a[i - 1] : 0);
15  }
16  for (const [l, r, x] of updates) {
17    diff[l] += x;
18    diff[r + 1] -= x;
19  }
20  const out: number[] = [];
21  let running = 0;
22  for (let i = 0; i < a.length; i++) {
23    running += diff[i];
24    out.push(running);
25  }
26  return out;
27}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

資料不會變、但要問很多次「某一段的總和」：先建前綴和，之後每次 O(1)。
要對很多段一起加值、最後才看結果：差分陣列讓每次更新只改兩格，最後一趟還原。
資料會一直變、又要隨時查詢：前綴和撐不住，改用線段樹或樹狀陣列。

和其他主題的關係

由這些組成: 資料結構 · 動態陣列
被這些用到: 考題：接雨水
延伸閱讀: 資料結構 · 線段樹與樹狀陣列雙指標與滑動視窗

時間與空間複雜度（Big O）

操作	平均	最差
建前綴和	O(n)	O(n)
區間總和查詢	O(1)	O(1)
差分陣列：區間加值	O(1)	O(1)
差分陣列：還原成數值所有更新做完後只做一次	O(n)	O(n)
改一個值後重建常常改值的話改用線段樹	O(n)	O(n)

空間：O(n)

Big O 實測：n 變大時步數怎麼長

數的是：每次查詢或更新讀寫的格子數（1,000 個隨機區間平均）

	Big O	n = 1,000	n = 4,000	n = 16,000	成長倍數：實測（理論）
直接加總一個區間	O(n)	334	1,334	5,334	×16 (×16)
前綴和查詢	O(1)	2	2	2	×1.0 (×1.0)
差分陣列的區間加值	O(1)	2	2	2	×1.0 (×1.0)

和其他做法比

	直接加總	前綴和（建表＋查詢）	倍數
n = 1,000，1,000 次查詢	334,337	3,000	×111
n = 100,000，100,000 次查詢	3,330,882,377	300,000	×11,103

隨機區間，數讀取的格子數。前綴和要先花 n 格建表，之後每次查詢只讀 2 格；查詢次數一多，建表的成本就攤掉了。值會變動的話前綴和得整個重建，那時改用線段樹或樹狀陣列。

真實世界裡的它

「和為 k 的子陣列」這類題目：前綴和加雜湊表，O(n) 數出所有符合的區間。
影像處理的積分圖（summed-area table）：二維前綴和，任何矩形的總和都是四個數加減。
航班訂位、排程這類「一段時間內加 x」的批次更新：差分陣列。

取捨與陷阱

差一的錯誤：prefix 比原陣列多一格，a[l..r] 是 prefix[r+1] − prefix[l]，不是 prefix[r] − prefix[l]。
總和可能溢位：大陣列的前綴和要用 64 位元整數（Java 的 long）。
差分陣列也要多一格，r + 1 才不會越界。

演算法