跳至主要内容

Prefix Sum

前綴和（Prefix Sum）是一種預先計算「從陣列開頭累加到每個位置的總和」 的技巧。準備好這張表之後，之後不管查詢幾次「任意區間的總和」，每一次都只需要 O(1)，不用再重新掃描一遍陣列。

白話理解

就像看銀行對帳單時，每一筆交易旁邊都會列出「目前累計餘額」。如果你想知道「3 月 5 日到 3 月 20 日之間總共花了多少錢」，不需要把這段期間的每一筆交易重新加一次，只要用「3 月 20 日的累計餘額」減去「3 月 4 日的累計餘額」就能瞬間算出來。

核心公式​

先建立一張前綴和陣列 prefix，其中 prefix[i] 代表「原陣列從第 0 個到第 i-1 個元素的總和」（習慣上會在最前面補一個 0，方便處理邊界）：

prefix[0] = 0
prefix[i] = prefix[i-1] + arr[i-1]

準備好之後，原陣列中「從 index i 到 index j（含頭尾）」的區間總和，可以直接用減法算出來：

sum(i, j) = prefix[j+1] - prefix[i]

實作​

def build_prefix_sum(arr):
    prefix = [0]  # 第 0 格補 0，代表「還沒加任何元素」
    for i in range(len(arr)):
        prefix.append(prefix[i] + arr[i])
    return prefix

def range_sum(prefix, i, j):
    return prefix[j + 1] - prefix[i]  # O(1) 查詢

逐步拆解：以 arr = [3, 1, 4, 1, 5, 9] 為例​

先建立前綴和陣列：

index0123456
arr-314159
prefix034891423

（prefix[i] 代表 arr 前 i 個元素的總和，例如 prefix[3] = 3 + 1 + 4 = 8）

現在想查詢 arr 中 index 2 到 4（也就是 [4, 1, 5]）的總和：

sum(2, 4) = prefix[4 + 1] - prefix[2] = prefix[5] - prefix[2] = 14 - 4 = 10

驗證一下：4 + 1 + 5 = 10，答案正確！而且不管查詢幾次、區間多長，每一次查詢都只需要一次減法，是 O(1)。

複雜度​

操作時間複雜度說明
建立 Prefix Sum 陣列O(n)只需要掃過一次原陣列
查詢任意區間總和O(1)直接查表相減
空間複雜度O(n)需要額外一個陣列儲存前綴和

如果沒有 Prefix Sum，每次查詢區間總和都要重新掃描一次該區間，單次查詢是 O(n)；如果需要查詢 m 次，總共會變成 O(n × m)。用 Prefix Sum 先花 O(n) 準備好之後，m 次查詢只需要 O(m)，資料量或查詢次數越大，優勢越明顯。

適用情況​

  • 多次查詢區間和 / 區間平均：例如成績系統要重複查詢「第 5 週到第 10 週的總銷售額」。
  • 子陣列和等於特定值：例如 Leetcode: Subarray Sum Equals K，通常會搭配 Hash Table 記錄「某個前綴和出現過幾次」，來快速判斷是否存在滿足條件的子陣列。
  • 二維矩陣的區間和查詢：概念可以延伸成 2D Prefix Sum，用來快速查詢矩陣中任意矩形範圍的總和（例如影像處理中的區域亮度加總）。

常見誤區​

  • index 對應關係搞混（off-by-one）：prefix 陣列通常比原陣列多一格（開頭補 0），查詢 sum(i, j) 時容易忘記要用 prefix[j + 1] 而不是 prefix[j]，動手前建議先用小範例驗證公式。
  • 原陣列被修改後，忘記重新計算 Prefix Sum：Prefix Sum 只適合「陣列內容固定、只需要查詢」的情境。如果陣列會被頻繁修改（更新某個元素的值），Prefix Sum 每次都要花 O(n) 重建，效率反而不好，這種情境通常會改用 Binary Indexed Tree（樹狀陣列）或 Segment Tree 這類進階資料結構。
  • 誤以為只能處理「總和」：Prefix Sum 的概念也能套用在其他滿足「結合律」的運算上，例如前綴的最大值、前綴的 XOR 值，思路都是一樣的。
  • 忘記處理查詢區間的邊界情況：如果 i = 0，代表要查詢「從頭開始」的總和，此時 sum(0, j) = prefix[j+1] - prefix[0] = prefix[j+1]，因為開頭補了 0，這種邊界情況不需要額外特判，這也是為什麼要在最前面補 0 的原因。
最後於 更新