這篇文章，會帶著大家複習以前學過的前綴和框架，
並且以區間和的概念與應用為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
前綴和 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
結語
好，今天一口氣介紹了最精華的部分，
通用的前綴和框架，還有相關的區間和衍伸題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
