很多「區間加總」與「有序陣列上的配對」不需要線段樹，也不需要二元搜尋。前綴和把重複的區間加總收成一次相減，差分把區間修改收成兩個端點，雙指標把有序陣列上的 (O(n^2)) 配對收成 (O(n))。三者都是後面 DP、線段樹與二分答案的前置工具，本站原先散落在各篇裡，沒有放在一起。

相關教材：Segment_Tree_Fenwick_Teaching_Materials.md（陣列會改、又要問區間時再升級）、Binary_Search_Teaching_Materials.md、Dynamic_Programming_Teaching_Materials.md。

目錄

  1. 前綴和
  2. 差分
  3. 二維前綴和
  4. 雙指標
  5. 滑動視窗
  6. 常見陷阱
  7. 練習題

1. 前綴和

令 prefix[0] = 0，prefix[i+1] = prefix[i] + a[i]。則索引 l 到 r（包含）的和是

[ \texttt{prefix}[r+1] - \texttt{prefix}[l] ]

陣列 a = [3, 1, 4, 1, 5]：

i 0 1 2 3 4 5
prefix 0 3 4 8 9 14

索引 1 到 3 的和是 1+4+1=6，也就是 prefix[4] - prefix[1] = 9-3=6。

建表 (O(n))，之後每次查詢 (O(1))。陣列若會改，前綴會整個失效，改用線段樹或樹狀陣列。

空區間 l > r 不要來減。l=0 時減到的是 prefix[0]=0，這就是把 0 放在前面的原因。

2. 差分

反過來：想對索引 l..r 全部加 d，不要真的跑一個迴圈。

差分配列 diff 與原陣列同長，一開始 0。一次區間加值只做

diff[l] += d
if r+1 < n: diff[r+1] -= d

全部加值做完，前綴和還原：a[i] = a[i] + diff 的前綴。多次區間加值的總成本是 (O(n+q))，而不是 (O(nq))。

例：a = [0,0,0,0,0]，對 1..3 加 2，對 2..4 加 1。

  • 第一次：diff[1] += 2，diff[4] -= 2 → [0, 2, 0, 0, -2]
  • 第二次：diff[2] += 1，r+1=5 超出，不減 → [0, 2, 1, 0, -2]

前綴還原：[0, 2, 3, 3, 1]。手算原陣列：索引 1 加 2，索引 2 加 2+1，索引 3 加 2+1，索引 4 加 1。一致。

差分適合「離線、最後才需要看出整條陣列」。若每次加值之後立刻要問區間和，這張表還沒還原，請改線段樹的懶標記。

3. 二維前綴和

矩陣 p[r+1][c+1] 是左上角子矩陣的和：

[ p[i+1][j+1] = a[i][j] + p[i][j+1] + p[i+1][j] - p[i][j] ]

減去 (p[i][j]) 是因為它被加了兩次。查詢以 ((r1,c1)) 為左上、((r2,c2)) 為右下的子矩陣：

[ p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1] ]

最後加回是因為那一塊被減了兩次。二維比一維容易在這裡漏加。

4. 雙指標

已排序陣列上，「兩個數相加是否為目標」不必雙重迴圈。

左指標從最小、右指標從最大：

  • 和太小：左指標右移，和只會變大。
  • 和太大：右指標左移，和只會變小。
  • 相等：找到一對。

例：[1, 2, 4, 7, 11]，目標 13。

左 右 和 動作
1 11 12 太小，左移
2 11 13 命中

每個指標最多走 (n) 步，時間 (O(n))，前提是已經排序。排序本身 (O(n\log n)) 時，總時間由排序決定。未排序就移動指標，單調性不在，會漏掉答案。

同一個骨架可以用在「合併兩個已排序串列」：誰小誰往前，這就是合併排序的合併步驟。

5. 滑動視窗

視窗是連續子陣列。右端一直往右擴，左端在「視窗已經不合法」時往右縮。兩端都只前進，時間 (O(n))。

最短的、和至少為 S 的連續子陣列。 a = [2, 1, 5, 2, 8]，(S=7)。右端每次進來一個數；只要視窗和仍然 (\ge 7)，就先記下長度，再丟掉左端。

動作 視窗 和 目前最短
加入 2、1 [2, 1] 3 尚無
加入 5 [2, 1, 5] 8 3
去掉 2 [1, 5] 6 3（已不合法，停止縮）
加入 2 [1, 5, 2] 8 3
去掉 1 [5, 2] 7 2
去掉 5 [2] 2 2（停止縮）
加入 8 [2, 8] 10 2
去掉 2 [8] 8 1
去掉 8 [] 0 1（停止縮）

最短長度是 1，對應子陣列 [8]。[5, 2] 是長度 2 的另一個合法視窗。若全程沒有合法視窗，答案是不存在。

和至少為 (S) 這個條件，在元素都是正數時，右擴會更合法、左縮會更不合法，所以指標只進不退。出現負數，和不再單調，這個滑動視窗會錯，要改前綴和加單調佇列，或直接 (O(n^2))。

6. 常見陷阱

  • 前綴下標差 1。 prefix[r]-prefix[l] 少算 a[l] 或多算 a[r]。先用本篇的 6 那個例子對一下。
  • 差分的右端點。 減的是 r+1，不是 r。減在 r 會讓 a[r] 自己被加又被減。
  • 二維容斥漏掉加回。 結果會少一塊。
  • 雙指標用在未排序陣列。 先排序，或改雜湊表的補數。排序會打亂原索引；題目若要原索引，排序時把索引一起帶上。
  • 滑動視窗遇到負數仍只用和。 單調性沒了。
  • 整數和溢位。 前綴用 64 位元。差分還原時同樣。

7. 練習題

  1. a=[3,1,4,1,5]，索引 0 到 4 的和、以及空的「從 2 到 1」為什麼不能用公式硬算？
  2. 差分配列長度 6，操作「0..2 加 1」「2..5 加 3」。還原後的陣列是什麼？
  3. [1, 3, 5, 8] 裡哪兩個數和為 9？雙指標的第一步和是多少？
  4. 為什麼滑動視窗求「和至少為 7」在陣列 [4, -10, 8] 會失敗？最短合法子陣列其實是哪一段？
  5. 什麼時候前綴和該升級成樹狀陣列？

參考答案

  1. 全陣列和是 prefix[5]-prefix[0]=14。l=2, r=1 時 r+1=2，prefix[2]-prefix[2]=0，公式會假裝空區間的和是 0，但呼叫端若認為區間存在就會算錯。先要求 l<=r。
  2. diff 起點為 0。diff[0]+=1，diff[3]-=1；diff[2]+=3，右端 5 的下一位超出長度，不減。diff=[1,0,3,-1,0,0]。前綴還原 [1,1,4,3,3,3]。索引 0、1 只吃到第一次，索引 2 兩次都吃到（1+3），索引 3..5 只吃到第二次。
  3. 1+8=9。第一步左 1 右 8，和已經是 9。
  4. 右端擴到 -10 時和變小，演算法會以為該縮左邊，但真正的答案是最後一個 [8]。負數讓「縮左邊一定讓和變小」不成立。
  5. 修改和查詢交錯、前綴要隨時正確時。靜態陣列或全部修改做完才查詢，前綴和與差分就夠。

小結

前綴和用一次相減回答靜態區間和。差分用兩個端點表示一整段加值，最後再前綴還原。雙指標與滑動視窗要求單調：排序陣列的兩數之和，或全正數的最短覆蓋。負數、即時修改、不可逆的區間運算，分別要把工具換成雜湊、線段樹，或乾脆放棄這個骨架。