# Python-LeetCode 581 第四招 前綴和 Prefix Sum
「前綴和應該怎麼做呀？我煩到好像要死掉了！」
「錢墜河跟鑰匙掉了都一樣，撿起來就好了呀！」
(這是前綴和一個有趣的梗圖)
## 基本原理
Prefix前綴，也翻譯為字首，就是字串或序列從頭開始到某個位置的連續一段，相對於prefix，suffix就是後綴或字尾。顧名思義，前綴和就是數列前面一段的總和。若 $nums[\;:n]$ 是一個整數序列，$prefix[i]$就是$sum(nums[\; :i+1])$，即前$i$項的總和。下面是一個例子。
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| - | - | - | - | - | - |-|
| nums | 2 | -5 | 3 | 2 | 1 | -2 |
| prefix-sum | 2 | -3 | 0 | 2 |3 | 1 |
我們這裡談的序列是離散函數，若類比到連續函數，$prefix$是$nums$積分，而$nums$是$prefix$的微分。前綴應用的題目頗多，這個單元會先談一些最直接的應用。最直接的應用就是區間和。
一個長度為$n$的數列，有$O(n^2)$個可能的區間$[i,j]$ for $0\leq i \leq j<n$。但只有$n$個prefix sum，若$psum[i]$為前$i$項的前綴和，則$[i,j]$區間和可以藉由前$j$項的總和減去前$i-1$項的總和來求出，即$psum[j]-psum[i-1]$，當然這裡$i>0$。若$i=0$，則$[i,j]$區間和就是$psum[j]$.
所以我們只要先計算並存好$n$個前綴和，就可以隨時得到$O(n^2)$個區間和的任何一個。而且，我們很容易在$O(n)$時間內算好所有的前綴和。
### Python計算儲存前綴和
以下是根據定義直接計算前綴和。
```python
psum = [0]*n
for i in range(n): psum[i] = sum(nums[:i+1])
```
很遺憾，這樣寫複雜度是$O(n^2)$。從DP(動態規劃)的觀點，前$i$項的總和可以由前$i-1$項的總和再加上第$i$項來得到。於是得到以下$O(n)$的方法
```python
psum = [0]*n
psum[0] = nums[0]
for i in range(1,n): psum[i] = psum[i-1]+nums[i]
```
也可以這樣寫
```python
psum = [nums[0]]
for i in range(1,n):
psum.append(psum[-1]+nums[i])
```
$psum[-1]$就是$psum$的最後一項。
要計算$[i,j]$區間和時
```python
rsum = psum[j]-psum[i-1] if i>0 else psum[j]
```
如果原序列nums不必保留，那可以更簡單的在原地計算前綴和
```python
for i in range(1,n): nums[i] += nums[i-1]
```
夠清楚夠乾淨的程式了，但這個 if 有點討厭，邊界檢查總是讓人心煩，有好的方式簡化嗎？
#### 哨兵 sentinel
簡化邊界檢查常用放哨兵的技巧，上個單元中，我們在Grid的邊界上放哨兵來省略邊界檢查，這裡我們也可以類似的做法。
如果我們在$psum$的最前方放一個0，index的定義移到區間$[1,n]$，那麼就不必檢查邊界了。常看到這樣的寫法：
```python
psum = [0]
for p in nums: psum.append(psum[-1]+p)
# find range sum [i,j]
rsum = psum[j+1]-psum[i] # index shift +1
```
吹毛求疵，這個方法還是有個缺點，index位移有時候忘記了就會犯錯。其實我們可以利用Python index -1 表示結尾的特性，把前方的哨兵0寫在後方。以下程式假設在原陣列中計算。
```python
for i in range(1,n): nums[i] += nums[i-1]
nums.append(0) # sentinel for [-1]
# find range sum [i,j]
rsum = nums[j]-nums[i-1] # index no shift
```
你可以發現$i=0$時，$nums[i-1]=nums[-1]=0$。
## 基本範例
LeetCode中有全裸的前綴和題目，直接要求實作online的區間和查詢。以下說明這兩個範例，一個是一維，一個是二維。
[(題目連結)303. Range Sum Query - Immutable (Easy)](https://leetcode.com/problems/range-sum-query-immutable/description/)
這個題目直接要求實作一個class來回覆區間和的查詢。解法就是上面說明的前綴和基本寫法，就不必多解釋了。
```python=
class NumArray:
def __init__(self, nums: List[int]):
self.prefix = [nums[0]]
for p in nums[1:]:
self.prefix.append(self.prefix[-1]+p)
self.prefix.append(0) #sentinel
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right]-self.prefix[left-1]
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)
```
### 二維前綴和
前綴和可以擴展到二維矩陣。每一個前綴和$psum[i][j]$定義是從左上角(0,0)到右下角(i,j)這個矩形區域的總和。當要計算左上角(r1,c1)到右下角(r2,c2)區域內總和時，可以根據簡單的排容原理來計算，請看下圖。
要計算紅色區塊的總和，我們可以用最大的那個矩形減去左邊綠色的，減去上方黑色的，再加回左上角淺藍色那一小塊(因為它被減去兩次)。下面請看LeetCode上二維前綴和的裸題。
[(題目連結)304. Range Sum Query 2D - Immutable (Medium)](https://leetcode.com/problems/range-sum-query-2d-immutable/description/)
題目是給一個矩陣後，每次要查詢子矩陣的總和。
計算二維前綴和有幾個類似的方式，這裡採用的是與計算區間和一樣的原理，把上面那個圖形中右下小角的紅色區塊看成只有一個元素時，大的矩形就是要求的前綴和，我們可以用上面的加上左邊的減去左上角的，最後加上紅色這個元素。因此，從上到下，由左而右掃描矩陣來計算即可。請看範例程式。
```python=
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m,n = len(matrix),len(matrix[0])
self.p = [row[:]+[0] for row in matrix]
self.p.append([0]*n)
for i in range(m):
for j in range(n): # row prefix sum
self.p[i][j] += self.p[i-1][j] + self.p[i][j-1] \
- self.p[i-1][j-1]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.p[row2][col2] - self.p[row1-1][col2] \
-self.p[row2][col1-1] + self.p[row1-1][col1-1]
# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
```
## 前綴與後綴
接著我們來看一個用到前綴與後綴的題目。後綴和與前綴和的道理是一樣的。
[(題目連結)2017. Grid Game (Medium)](https://leetcode.com/problems/grid-game/description/)
這個題目是說有一個$2\times n$的矩陣，有兩個人玩遊戲，要從左上角走到右下角，每一步只能往右或往下，第一個人先走，走過的地方分數就會變成0，目標是讓第二個人的分數越小越好。
請注意矩陣只有兩列。
其實第一個走的路徑只有$n$種，也就是只要看他在哪個column由第一列走到第2列，第二個人可以得到的分數就是第一列與第二列剩下較多的。
如上圖，假設箭頭是第一個人的路徑，第二個人的分數就是紅色與橙色區域比較大的，所以我們只要min(max(紅色,橙色))就是答案。
我們先計算出第一列所有的後綴和，以及第二列的所有前綴和，然後對所有的$i$，找兩者較大的最小值，要注意邊界。
以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
# going down at column i, score =
# #max(suffix[i+1] of row 0, prefix[i-1] row 1)
def gridGame(self, grid: List[List[int]]) -> int:
n = len(grid[0])
if n==1: return 0
for i in range(n-2,0,-1):
grid[0][i] += grid[0][i+1] # suffix sum
for i in range(1,n):
grid[1][i] += grid[1][i-1] # prefix sum
imin = min(grid[0][1], grid[1][n-2]) # col 0 and col n-1
for i in range(1,n-1):
imin = min(imin, max(grid[0][i+1],grid[1][i-1]))
return imin
```
## 前綴+搜尋
前綴和搭配搜尋的題目很多。典型的題目是由前掃到後，一路走一路計算前綴和，並在之前的前綴和中搜尋。
[(題目連結)560. Subarray Sum Equals K (Medium)](https://leetcode.com/problems/subarray-sum-equals-k/description/)
題目是給一個整數數列以及一個整數$k$，要求出有多少subarray其和恰為$k$。
subarray是指陣列中連續的一段區間，所以就是要找區間和，如果前$i$項的和是$psum[i]$，那麼就是要找有多少個$j$，滿足$j<i$且$psum[i]-psum[j-1]==k$。
如果這題陣列元素都是正的，對固定一端的區間和將會是單調上升(或下降)，那麼可以用二分搜來找是否有對應區間和為$k$，這種情形用滑動視窗也可以做。這題的陣列數值有正有負，沒有單調性，不過他要找的和是恰為$k$，搜尋除了有順序的二分搜之外，還可以運用字典搜尋。
將$i$由左至右逐步滑行，之前的所有前綴和放在一個字典中，我們在字典中搜尋$psum[i]-k$有幾個，就是以$i$為右端有幾個區間和為$k$。要記錄成員的個數，我們的字典以數值當key，對應欄位給個數。以下的範例程式我們用Counter()，用一般字典也可以。
```python=
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
d = Counter() # d[p] = number of prefix sum with value p
d[0] = 1
psum = total = 0
for v in nums:
psum += v # prefix sum
total += d[psum-k]
d[psum] += 1
return total
```
前綴和是逐步算出，且不必另外儲存，第7行計算前綴和，第8行將字典中$psum-k$的個數加進total中，第9行再將自己的前綴和放入字典中，結束這一回合。
小心要先查詢後記錄，因為題目要求子陣列必須非空，若$k=0$時不能搜到自己。
再看一題類似的題目。
[(題目連結)523. Continuous Subarray Sum (Medium)](https://leetcode.com/problems/continuous-subarray-sum/)
這題也是給一個陣列以及一個整數$k$，問是否存在一個長度至少為2的子陣列其和是$k$的倍數。也就是說，是否存在區間$[i,j]$，滿足$(prefix[j]-prefix[i-1])%k==0$，等價於$prefix[j]$與$prefix[i-1]$除以$k$的餘數相同。
因此，我們可以一路掃過去，把之前的前綴和除以$k$的餘數都放入集合中，每次去集合中搜尋是否存在相同的餘數即可。
如果去看一下題目的通過率，會發現相對較低，我的猜想是這題有個陷阱，就是長度必須至少為2，沒注意會誤判。處理的方式不只一種，這裡採取的方式很簡單，就是第一單元中提到的「避免踩到自己」的原則，也就是那個「羊往前走，屎往後拉才不會踩到」的小故事。
下面範例中，我們用原陣列的位置計算前綴和，在第$i$步結束時，我們才將$i-1$的前綴和加入，自然搜尋到的長度至少為2。
```python=
class Solution:
# find same remainder of prefix sum
# avoid searching singleton, starting from nums[1] and insert i-1 at i
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
nums[0] %= k
d = {0} # 0 for null prefix
for i in range(1,len(nums)):
nums[i] = (nums[i]+nums[i-1])%k # prefix sum
if nums[i] in d: return True
d.add(nums[i-1])
return False
```
#### 二維的例子
接下來看一個二維陣列的題目。
[(題目連結)1074. Number of Submatrices That Sum to Target (Hard)](https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/)
本題中，輸入一個$m\times n$矩陣以及一個整數$target$，要找出有多少個子矩陣其和恰為$target$。跟前一題很像，只是一維陣列改成了二維陣列。
既然一維陣列會做，那麼我們可以用類似的方法來解二維陣列的問題。我們嘗試枚舉所有列的區間，對於一組列區間，將這些列合併加總變成一列，然後再用一維陣列的方法來解。在枚舉所有列區間的時候，我們適當的安排順序，可以使得每一個列區間的合併只耗費$O(n)$的時間就可以從前一個列區間得到，而前述一維的方法也是線性的時間複雜度。因為所有列區間的數量是$O(m^2)$，整個時間複雜度就是$O(m^2n)$。
為了應付$m>>n$的情形，下面的範例程式中，我們在$m>n$時先將矩陣轉置(Transpose)。
```python=
class Solution:
#O(m^2*n) m<=n; enumerate i<=j, sum up matrix[i:j] to one row
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
m,n = len(matrix),len(matrix[0])
if m>n: #transpose
t = [[row[j] for row in matrix] for j in range(n)]
t,matrix = matrix,t
m,n = n,m
total = 0
for i in range(m):
s = [0]*n # the combined row from i to some j
for row in matrix[i:]: # all matrix[i:j]
cnt = Counter({0:1}) # dict for previous prefix sum
prefix = 0 # current prefix sum
for k in range(n): # sweep column by column
s[k] += row[k]
prefix += s[k]
total += cnt[prefix - target]
cnt[prefix] += 1
#end for-i
return total
```
## 組合技範例：單調隊列+前綴和
題目如果搭配了多個技巧，往往就變得比較難。這裡我們示範其中一題，這一題是前綴和搭配了「單調隊列」。考慮到有些人尚未了解單調隊列，我們先拿一題單調隊列的題目來做說明。未來會有另外一個單元專門講單調隊列。
### 單調隊列基本型範例
下面這一題是典型的單調隊列。
[(題目連結)239. Sliding Window Maximum (hard)](https://leetcode.com/problems/sliding-window-maximum/)
題目說有一個長度為$k$的sliding window在一序列中一步一步移動，請計算出在每一個位置時的區間最大值。題目名稱有sliding window，但並非用該技巧。
其實要算的是$[max(nums[0:k])), max(nums[1:k+1]),\ldots ]$，也就是所有$n-k+1$個長度為$k$的區間的每一個區間最大值。當然，直接這麼寫的時間複雜度是$O(kn)$，太慢了。
單調隊列背後的道理可以以下面情境來打個比方。
「學生一屆一屆的進入學校，小明很喜歡程式比賽，當他進入學校時，如果有學長姐厲害到小明難以超越，那沒關係，小明在學校還是有出頭之日，因為學長姐會比他先畢業。但如果在小明之後新進來一位他無法超越的學弟妹，那完蛋了，小明在該校沒有什麼機會獨領風騷了，因為他會先畢業。」
我們的window在序列一步一步右移，可以看成一屆有一位學生進入，視窗長度固定為$k$，也就是學生進入後$k$屆就會畢業，同時在校的也恰有$k$位，我們要找出每一年最厲害的校內冠軍。
上面的例子告訴我們，對於某個$i$(小明)，如果同時在視窗內有個$j$，$nums[j]>nums[i]$，如果$j<i$，則 $i$ 尚未絕望，將來還有可能有機會當冠軍；但如果$j>i$，則 $i$ 從此刻起永遠不會是校內冠軍了。
如果我們把視窗內這些不可能成為冠軍的去除不看，那麼視窗內的將是個單調下降的子序列(monotonically decreasing subsequene)。這就是**單調隊列**。
我們用一個容器存放目前的隊列，維護的迴圈不變性是：
1. 隊列是遞減的
2. 隊列中均為尚在範圍內的元素
請注意，**根據迴圈不變性，隊列最前方的就是區間最大值**。每次新元素進入時，我們做兩件事：
1. 新生刪除所有不比自己強的學長姐。根據迴圈不變性，隊列為遞減的，我們只要從後往前刪除比新元素小的成員，當碰到第一個大於他的元素，刪除動作即已完成，因為前面的更大。刪除完成後再將自己加入隊列尾端(新生永遠有希望)。
2. 檢查最前方，也就是最大的元素是否已經出界，若是，將其移除。
要使用什麼容器來存放隊列呢？因為要支援前方與後方的移除，典型的做法是用deque(double ended queue雙向佇列)。Python也有提供deque，我個人比較喜歡用list加上一個head變數記錄頭端的位置即可。因為list尾端的刪除與新增都是$O(1)$，所以很方便。
來看本題的範例程式。
```python=
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = [] # (value,index) decreasing subsequence
head = 0
ans = []
for i,x in enumerate(nums):
while head<len(q) and q[-1] < (x,i):
q.pop()
q.append((x,i))
if q[head][1] <= i-k: # remove out of date
head += 1
if i>=k-1: ans.append(q[head][0])
return ans
```
因為需要偵測出界，這裡隊列的每個成員我們用一個tuple來存他的值與位置。當然也可以只存index然後用原陣列去抓值，也可以用兩個list。第6行逐一掃瞄新進成員，第7 ~ 8行執行尾端刪除，第9行將新進成員尾端加入，第10 ~ 11行檢查前端是否出界。
時間複雜度：$O(n)$，線性。
### 單調隊列+前綴和
回到本單元主題前綴和，以下這題是搭配前綴和與單調隊列的難題。
[(題目連結)862. Shortest Subarray with Sum at Least K (Hard)](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/)
題意很簡單，給一個數列以及一個整數$k$，找出區間和不小於 $k$ 的最短非空區間長度。參數範圍：
* $1 \leq nums.length \leq 10^5$
* $-10^5 \leq nums[i] \leq 10^5$
* $1 \leq k \leq 10^9$
如果陣列數值均為正，我們可以用sliding window去推。但本題陣列數值有正有負，區間和沒有單調性。從區間和與前綴和的關係下手，對於 $i$ 結尾的區間來說，我們要找的是最大的$j<i$，滿足$prefix[i]-prefix[j]\geq k$，也就是說，在掃描到 $i$ 之前的前綴和之中，越小的越好，越晚出現的越好，這就是單調隊列了。
我們逐步掃描陣列，計算前綴和，將單調隊列維護好，因為越小越好，這裡的單調隊列是遞增的。前端何時出界呢？一個左端如果已經找到一組解，就不必再用它了，因為右端是遞增，再用它的解不會更好只會更差(更長)。以下是範例程式。
```python=
class Solution:
# monotonic queue for prefix sum
# previous prefix sum: smaller is better, later is better
def shortestSubarray(self, nums: List[int], k: int) -> int:
n = len(nums)
que = [(0,-1)]; head=0 #[val,idx] monotonic deque
psum = 0 # prefix sum
ans = n+1
for i,s in enumerate(nums):
psum += s
# pop out useless
while head<len(que) and que[-1][0] >= psum:
que.pop()
que.append((psum,i))
# check answer from head
while psum-que[head][0] >= k: # k>=1, nerver empty
ans = min(ans, i-que[head][1])
head += 1 # left become useless after finding partner
#end for
if ans==n+1: return -1
return ans
```
稍微留意，在第14行我們將 $i$ 的前綴和由尾端加入，因為這題的$k\geq 1$，我們不必擔心搜尋到自己，同樣的，第16行的while不必檢查佇列是否已經全空。
## 結語
前綴和是簡單而又很有用的技巧，最常出現的是尋找區間和。常見的有一維與二維的前綴和，事實上更高維也是一樣的道理，只是更煩而已。
前綴和搭配一路掃描一路搜尋是很常見的題型，這時常用到字典，集合或表格來搜尋，也可能搭配二分搜的情形。
前綴和還有些延伸本單元沒談到，例如前綴的不是和，而是prefix maximum/minimum。計算動態prefix sum常用的進階資料結構Binary Indexed Tree，甚至線段樹，也很值得介紹，所謂動態是指陣列資料可能改變的情形。另外有些題目可以運用prefix sum與差分是反運算的觀念來做，這些將來應該都會有另外的單元來討論。
Sign in with Wallet
Connect another wallet