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

Viktor Ritsvall on Unsplash

這篇文章，會帶著大家複習以前學過的前綴和框架，

並且以區間和的概念與應用為核心，

貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。

前綴和 prefix sum框架 與 區間和計算的關係式

詳細的推導過程可參考這部教學影片

接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目

(請讀者、或觀眾留意上面的這種 前綴和 框架，之後的解說會反覆出現)

Range Sum Query - Immutable 一維的區間和

基本上就是前綴和框架的標準應用，直接使用推導出來的區間和關係式即可。

由前綴和快速計算一維的區間和

class NumArray:

    def __init__(self, nums: List[int]):
        
        self.size = len(nums)
        

        # build prefix sum table when input nums is valid
        self.s = [ 0 for _ in range(self.size) ]

        self.s[0] = nums[0]

        # s[k] = nums[0] + ... + nums[k]
        # s[k] = s[k-1] + nums[k]
        for k in range(1,self.size):
            self.s[k] = self.s[ k-1 ] + nums[ k ]
        

    def sumRange(self, i: int, j: int) -> int:
        

        # lookup table from prefix sum table, s
        if i == 0:
            return self.s[ j ]
        else:
            return self.s[ j ]-self.s[ i-1 ]

好，接下來看一個推廣應用

Find Pivot Index 尋找左右平衡的軸心點

題目要求我們找出index i 使得 A[0] + ... A[i-1] = A[i+1] + ... + A[n]

也就是左右平衡的軸心點位置。

等價於 A[0, i-1] 的區間和 = A[i+1, n]的區間和

既然我們已經知道任意給定區間的區間和快速計算方式，那這邊也是同樣道理。

先建立前綴和表格，接著用前綴和表格查表計算左區間和 與 右區間的和，
當兩者相等時，當下的index i 就是平衡軸心點。

由前綴和快速計算兩個一維的區間和

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        
        # s = prefix sum of array
        # s[i] = nums[0] + nums[1] + ... + nums[i]
        s = list( itertools.accumulate(nums) )
        total_sum = sum( nums )

        # Linear scan on each index
        for i in range( len(nums) ):

            left_sum = s[i-1] if i >= 1 else 0
            right_sum = total_sum - s[i]

            # Find pivot index from definition
            if left_sum == right_sum:
                return i

        return -1

再來看一個進階應用。

Subarray sum Equals k

題目問有多少個子陣列，他們的區間和恰好=k。

那這題就會用到之前學會的技巧，用前綴和去高速計算區間和。

並且額外運用一個觀念:

如果前綴和S，與S+k都曾經出現過，代表必定存在某個區間，他們的區間和恰好為k。

還有另一個等價的說法，

如果前綴和S，與S - k都曾經出現過，代表必定存在某個區間，他們的區間和恰好為k。

範例與示意圖:

image

搭配字典與前綴和的解題程式碼:

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        
        # prefix sum
        cur_prefix_sum = 0
        
        # counter of subarray with sum = k
        counter = 0
        
				# key: subarray prefix sum
				# value: occurrence of given prefix sum
        prefixSum_map = defaultdict(int)
		
				# prefix summation 0 is reached by selecting nothing
        prefixSum_map[0] = 1
        
        for number in nums:
            
							# update prefix sum from first element to current position
            cur_prefix_sum += number
            
							# if curPrefixSum - k exist in map, then sub array with sum = k must exist in somewhere
            if (cur_prefix_sum - k) in prefixSum_map:
                counter += prefixSum_map[cur_prefix_sum - k]
            
							# update occurrence of curPrefixSum
            prefixSum_map[cur_prefix_sum] += 1
            
        return counter

同樣的觀念推廣到二維區間和的計算，也是可以的唷!

給個具體的例子幫助理解 (下圖來自wiki)

image

對應的例題就是

Range Sum Query 2D - Immutable 二維的區間和

類似的操作，一樣是先建立前綴和表格，接著查表快速計算指定範圍的二維區間和。

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        
        if not matrix:
            # Reject empty matrix
            return
        
        # get height and width of matrix (also known as image)
        h, w = len(matrix), len(matrix[0])
        
        # build integral image by recurrence relationship    
        self.integral_image = [ [ 0 for _ in range(w) ] for _ in range(h) ]
        
        for y in range(h):

            summation = 0

            for x in range(w):

                summation += matrix[y][x]
                self.integral_image[y][x] = summation

                if y > 0:
                    self.integral_image[y][x] += self.integral_image[y-1][x]      

        return
                    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        
        bottom_right    = self.integral_image[row2][col2]
        bottom_left     = self.integral_image[row2][col1-1] if col1 >= 1 else 0
        top_right       = self.integral_image[row1-1][col2] if row1 >= 1 else 0
        top_left        = self.integral_image[row1-1][col1-1] if col1 >= 1 and row1 >=1 else 0
        
        return bottom_right - bottom_left - top_right + top_left

結語

好，今天一口氣介紹了最精華的部分，

通用的前綴和框架，還有相關的區間和衍伸題與演算法建造，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~