Prefix Sum前綴和
預先累加，區間和變成一次減法。
用在：報表區間加總、子陣列和問題
01為什麼需要它
每天一筆營收，老闆隨時會問任意區間的總和，一天問幾百次。每次都從頭加到尾，資料一多就等很久。
為什麼用它先花 O(n) 算一次「從第一天累計到每一天」的前綴和，之後任何區間都是兩個累計值相減，O(1)。
找出陣列裡「和等於 k」的連續子陣列有幾個。暴力枚舉所有 (l, r) 是 O(n²)，n 十萬就爆了。
為什麼用它區間和 = 兩個前綴和的差。走到位置 j 時，只要問「前面有幾個前綴和等於 P[j] − k」，用雜湊表記次數，整體 O(n)。
積分影像（integral image）是電腦視覺的基本工具：要快速算出圖片任一矩形區域的像素總和，用在人臉偵測、模糊濾鏡。
為什麼用它二維前綴和：一次 O(mn) 建表，之後任何矩形的和只要四個值加減，O(1)。
看到這些關鍵字就想到它：區間和、連續子陣列的和、多次查詢同一份不變的資料、矩形區域總和、和等於 k。
02核心概念
前綴和是「從頭累加到每個位置」的陣列：P[i] = a[0] + a[1] + … + a[i-1]，多留一格 P[0] = 0。這樣任意區間 a[l..r] 的和就是 P[r+1] − P[l]：到 r 為止的總和，減掉 l 之前的總和，中間那段就留下來了。
它是最單純的預處理換查詢：建表 O(n) 做一次，之後每次查詢 O(1)。前提是資料不會改，因為改動一個 a[i] 會讓後面所有 P 都要更新。若資料常改又常查，就要升級成 Fenwick 樹或線段樹，那是樹那一章的事。
多留 P[0] = 0 這一格很重要，它讓「從 0 開始的區間」不用特判。同樣的想法可以延伸：前綴最大值、前綴 XOR、前綴乘積（Product of Array Except Self 就是前綴乘積乘上後綴乘積），只要運算有「反操作」或只要單向累積就行。
03演算法步驟
- 1開一個長度
n + 1的陣列，P[0] = 0。 - 2從左到右，
P[i+1] = P[i] + a[i]。每一步只做一次加法，建表 O(n)。 - 3查
a[l..r]的和：回傳P[r+1] − P[l]。注意右邊界是 r+1，因為 P 的定義「不含」該位置。 - 4題目問「和等於 k 的子陣列」時，改寫成
P[j] − P[i] = k，邊掃邊用雜湊表記錄每個前綴和出現幾次，走到 j 就查P[j] − k出現過幾次。記得先放{0: 1}。 - 5二維時
S[r+1][c+1] = grid[r][c] + S[r][c+1] + S[r+1][c] − S[r][c]（容斥：左邊加上面，扣掉重複的左上角），查矩形也是同樣的四項加減。
04互動示範
先按「建表下一步」看 P 怎麼一格一格累加，建好後選 l 和 r，看區間和怎麼從兩個 P 值相減得到。
05程式碼
三段：基本的建表與查詢、前綴和加雜湊表數子陣列、二維前綴和。C++ 用 long long 存前綴和，避免累加溢位。
# 建表 O(n)：P[i] = a[0] + ... + a[i-1]，多留一格 P[0] = 0
def build_prefix(a):
p = [0] * (len(a) + 1)
for i, x in enumerate(a):
p[i + 1] = p[i] + x
return p
# 查詢 O(1)：a[l..r] 的和
def range_sum(p, l, r):
return p[r + 1] - p[l]
a = [3, 1, 4, 1, 5, 9, 2, 6]
p = build_prefix(a) # [0, 3, 4, 8, 9, 14, 23, 25, 31]
range_sum(p, 2, 5) # 4+1+5+9 = 19 = p[6] - p[2]
# 前綴和 + 雜湊表：有幾個子陣列的和恰好是 k（LeetCode 560）
# 子陣列 (i, j] 的和 = P[j] - P[i] = k ⇔ P[i] = P[j] - k
# 所以走到 j 時，問「之前有幾個前綴和等於 P[j] - k」
def subarray_sum(nums, k):
count = 0
seen = {0: 1} # 前綴和 0 出現過一次（空前綴）
running = 0
for x in nums:
running += x
count += seen.get(running - k, 0)
seen[running] = seen.get(running, 0) + 1
return count
# 二維前綴和：S[r][c] = 左上角到 (r-1, c-1) 的矩形總和
def build_2d(grid):
m, n = len(grid), len(grid[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for r in range(m):
for c in range(n):
s[r+1][c+1] = grid[r][c] + s[r][c+1] + s[r+1][c] - s[r][c]
return s
def rect_sum(s, r1, c1, r2, c2): # 左上 (r1,c1) 到右下 (r2,c2)
return s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1]06練習題
- LeetCode 303Range Sum Query - ImmutableEasy
- LeetCode 724Find Pivot IndexEasy
- LeetCode 560Subarray Sum Equals K（前綴和 + 雜湊表）Medium
- LeetCode 304Range Sum Query 2D - ImmutableMedium
- LeetCode 974Subarray Sums Divisible by KMedium