➕用Python來實現 Prefix sum 前綴和

Photos by Lanty on Unsplash

定義

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

合縱連橫: 從區間和應用理解 前綴和 的本質

前綴和應用: 尋找旅途中的海拔最高點_Leetcode #1732 精選75題解析