定義
Prefix Sum（前綴和）是一種用於計算陣列中任意區間和的高效方法。
前綴和算是一種犧牲空間換取時間效能提升的策略。
這在需要頻繁查詢區間和的情況下特別有用。
一開始，初始化時花費O(n)時間，掃描每個元素累加，建立一個prefix sum table，
接著，提供query介面，提供使用者查詢任意的區間和，並且能夠在O(1)得到答案。
示意圖
優點
1.提升區間和查詢效能，可以在O(1)時間內計算並且得到任意區間和。
缺點
1.需要額外花費O(n)空間來建立prefix sum table。
2.事前需要花費O(n)時間掃描每個陣列元素累加，建立prefix sum table。
Prefix Sum的class定義 與 初始化
class PrefixSum:
def __init__(self, arr):
# 建構子
self.prefix_sums = self._compute_prefix_sums(arr)
def _compute_prefix_sums(self, arr):
# 事先花費O(n)時間計算前綴和
prefix_sums = [0 for _ in range(len(arr)) ]
prefix_sums[0] = arr[0]
for i in range(1, len(arr)):
prefix_sums[i] = prefix_sums[i - 1] + arr[i]
return prefix_sums
Prefix Sum常見的操作
1.查詢區間和 range_sum(left, right)
如果left 是零，代表左邊端點是起點，直接返回self.prefix_sums[right]即可。
如果left非零，利用區間和抵銷的觀念，計算
self.prefix_sums[right] - self.prefix_sums[left-1] 得到區間和。
時間複雜度: O(1)
def range_sum(self, left, right):
if left == 0:
return self.prefix_sums[right]
else:
return self.prefix_sums[right] - self.prefix_sums[left-1]
測試範例
完整的Prefix sum實作和程式碼
class PrefixSum:
def __init__(self, arr):
self.prefix_sums = self._compute_prefix_sums(arr)
def _compute_prefix_sums(self, arr):
prefix_sums = [0 for _ in range(len(arr)) ]
prefix_sums[0] = arr[0]
for i in range(1, len(arr)):
prefix_sums[i] = prefix_sums[i - 1] + arr[i]
return prefix_sums
def range_sum(self, left, right):
if left == 0:
return self.prefix_sums[right]
else:
return self.prefix_sums[right] - self.prefix_sums[left-1]
def test():
# Demo
arr = [3, 4, 1, 7, 9, 1]
prefix_sum = PrefixSum(arr)
print("Input array :", arr)
print("Prefix sum :", prefix_sum.prefix_sums)
print("\nSum of range (1, 3):", prefix_sum.range_sum(1, 3))
print("Sum of range (0, 5):", prefix_sum.range_sum(0, 5))
if __name__ == '__main__':
test()
測試輸出
Input array : [3, 4, 1, 7, 9, 1]
Prefix sum : [3, 7, 8, 15, 24, 25]
Sum of range (1, 3): 12
Sum of range (0, 5): 25
結語
其實前綴和就是陣列元素的累加，而區間和就是區間元素的累加，
透過事前額外的計算建表，提升run-time 區間和的查詢與計算效能。
讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，
會有更深刻的了解和體會！
Prefix sum相關的演算法練習題與詳解
前綴和應用: 指定目標值的子陣列數目 Binary Subarrays With Sum_Leetcode #930
前綴和應用: 總和=k的子陣列有幾個 Subarray Sum Equals K_Leetcode #560