想象一下，你有一個裝滿數字的數組，比如 [1, 2, 3, 4, 5]。現在，老師給你出了一個問題：“請快速算出從第 2 個數字到第 4 個數字的和是多少？”
你可能會想：“這還不簡單嗎？直接把 2 + 3 + 4 加起來就行了，等於 9。” 但如果老師問的是“從第 1 個到第 5 個數字的和”，或者“從第 3 個到第 100 個數字的和”，甚至“有 1000 次這樣的問題”，每次都從頭算一遍，就會非常麻煩。有沒有更聰明的辦法呢？
這時候，前綴和數組就能派上用場了！
什麼是前綴和數組？¶
前綴和數組（Prefix Sum Array）是一個輔助數組，它的每個元素表示原數組中前若干個元素的和。
比如，原數組是 A = [1, 2, 3, 4, 5]，我們可以構造一個前綴和數組 S，其中：
- S[0] = 0（代表“前 0 個元素的和”，初始值）
- S[1] = A[1] = 1（前 1 個元素的和）
- S[2] = A[1] + A[2] = 1 + 2 = 3（前 2 個元素的和）
- S[3] = A[1] + A[2] + A[3] = 1 + 2 + 3 = 6（前 3 個元素的和）
- S[4] = A[1] + A[2] + A[3] + A[4] = 1 + 2 + 3 + 4 = 10（前 4 個元素的和）
- S[5] = A[1] + A[2] + A[3] + A[4] + A[5] = 1 + 2 + 3 + 4 + 5 = 15（前 5 個元素的和）
所以，前綴和數組 S 就是 [0, 1, 3, 6, 10, 15]。
如何用前綴和數組計算區間和？¶
假設我們想計算原數組中從第 i 個元素到第 j 個元素的和（這裏 i 和 j 是原數組的索引，且 1 ≤ i ≤ j ≤ n，n 是原數組長度）。
根據前綴和數組的定義：
- S[j] 是前 j 個元素的和（即 A[1] + A[2] + ... + A[j]）
- S[i-1] 是前 i-1 個元素的和（即 A[1] + A[2] + ... + A[i-1]）
那麼，這兩個和相減，就能得到從第 i 個到第 j 個元素的和：
區間和 = S[j] - S[i-1]
舉個例子驗證¶
用剛纔的數組 A = [1, 2, 3, 4, 5]，計算區間 [2, 4]（即第 2 到第 4 個元素的和）：
- 原數組元素：A[2] = 2，A[3] = 3，A[4] = 4，和爲 2 + 3 + 4 = 9
- 前綴和數組 S = [0, 1, 3, 6, 10, 15]
- 根據公式：S[4] - S[1] = 10 - 1 = 9，結果完全正確！
爲什麼前綴和這麼快？¶
如果不用前綴和，每次計算區間和都需要從頭加到尾，時間複雜度是 O(j - i + 1)（區間長度）。如果有 q 次查詢，總時間就是 O(q * n)。
而用前綴和：
- 預處理前綴和數組的時間是 O(n)（遍歷原數組一次）
- 每次查詢區間和的時間是 O(1)（只需一次減法）
- 總時間複雜度是 O(n + q)，比直接計算快得多！
注意事項¶
- 索引對齊：要注意原數組和前綴和數組的索引對應關係。如果原數組是從 0 開始的（比如
A[0] = 1，A[1] = 2），前綴和數組的定義會稍有不同，但核心公式類似（此時區間和 = S[j+1] - S[i]）。 - 區間合法性：確保查詢的區間
[i, j]有效（i ≥ 1，j ≤ n），否則會導致計算錯誤。 - 空間換時間：前綴和數組需要額外的空間存儲，空間複雜度是 O(n)，但換來的是時間的極大優化。
總結¶
前綴和數組是一個簡單又實用的數據結構，它通過“提前計算累積和”，將區間和的查詢時間從 O(n) 降到 O(1)。核心思想是：用空間換時間，預處理一次，查詢零次，非常適合處理“多次區間和查詢”的問題。
現在，你是不是覺得前綴和數組變得簡單易懂了？試着用自己的數組構造一個前綴和數組，然後計算幾個區間和，感受一下它的神奇之處吧！