## 前綴和定義
前綴和的定義就是各個元素到起點的總和，下圖的陣列 A 對應的前綴和就是 P
假如有一個陣列 $A$，裡面有 $n$ 項，假設它的前綴和為陣列 $P$
那麼 $P$ 看起來會像這樣
```cpp=
P[0] = A[0]
P[1] = A[0] + A[1]
P[n-1] = A[0] + A[1] + ... + A[n-1]
```
而後綴和其實就是各個元素到終點的總和
```cpp=
P[n-1] = A[n-1]
P[n-2] = A[n-1] + A[n-2]
P[0] = A[n-1] + A[n-2] + ... + A[0]
```
所以任一位置的前綴和都可以說是 : 上一個位置的前綴和 + 目前位置的值
當然為了避免在計算第一個位置時超出範圍，我們可以在最前方加入一個 $0$
通常來說一般在計算前綴和都是使用一個 for-loop
```cpp=
vector<int> A = {1, 2, 3, 4, 5} ;
vector<int> P(5) ;
P[0] = A[0] ;
cout << P[0] << ' ' ;
for (int i=1;i<A.size();i++) {
P[i] = P[i-1] + A[i] ;
cout << P[i] << ' ' ;
}
```
前綴和最基本的題目就是從定義解題，但是之後的延伸題會加入其他的東西
尤其許多題目會與區間有關連，這時候前綴和最好在前方加入一個 $0$ 表示無任何元素時的前綴和
## P-1 等值首尾和
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d563)
假設有一個陣列 $x$，它有 $n$ 個元素，每一個都大於零
我們說 `x[0]+x[1]+...+x[i]` 是個前綴和(Prefix Sum)，而`x[j]+x[j+1]+...+x[n-1]`則是個後綴和(Suffix Sum)
請寫一個程式，求出 $x$ 中有多少組相同的前綴和與後綴和
解題思路:
圖片
首先題目要求找到前綴和後綴和的相同值有幾組
可是如果題目中有相同的組合(例如:兩組 $3+6+2$ 都等於 $11$ )這樣只算是 $1$ 組
而且因為每一項都大於零，所以前綴和往後只會越來越大，後綴和往前只會越來越小
所以在找數字 $x$ 的時候，後綴和只要從最後面往前找就行，如果還要找 $x+y$ 的數字
那只要在原本找到 $x$ 的地方再往前找即可
用程式碼看起來就像這樣：
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
cin >> n ;
vector<int> A(n), pre(n), suf(n) ; // 數值、前綴和、後綴和
for (int i=0;i<n;i++)
cin >> A[i] ;
pre[0] = A[0], suf[n-1] = A[n-1] ;
for (int i=1;i<n;i++) {
pre[i] = pre[i-1] + A[i] ; // 計算前綴和
suf[n-i-1] = suf[n-i] + A[n-i-1] ; // 計算後綴和
}
int idx = n-1, ans = 0 ;
for (int i=0;i<n && idx >= 0;i++) {
while (idx >= 0 && pre[i] > suf[idx]) // 往前找
idx-- ;
if (idx != -1 && pre[i] == suf[idx]) // 找到了
ans++ ;
}
cout << ans ;
return 0 ;
}
```
## P-2 區間和練習
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e346)
給定一個長度為 $n$ 的整數序列 $A$，請回答 $q$ 筆詢問
每筆詢問會問其中一段連續區間的總和為何
解題思路：
區間和可以利用前綴和計算而成
拿範例輸入來說，設前綴和為陣列sum
因為他給的區間是從 1 開始，而我們的 index 是從 $0$ 開始，所以他給的數字要 $-1$
`sum[ 1 ] = A[ 0 ] + A[ 1 ]`
`sum[ 4 ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + A[ 3 ] + A[ 4 ]`
`sum[ 5 ] - sum[ 1 ] = A[ 2 ] + A[ 3 ] + A[ 4 ]`
也就是 [ $3,5$ ] 的**區間和**，上述式子可以看出**前綴和跟區間和的關係**
用程式碼看起來就像這樣：
```cpp=
cout << sum[5] - sum[3-1] << '\n' ;
```
區間和可能有 [ $1,n$ ] 在這種狀況下 $1-2 = -1$ 會導致輸出錯誤
所以我們在前綴和前面加上一項 $0$
並且因為前綴和多了一項，我們也要新增預設
```cpp=
prefix_sum[0] = 0 // 前綴和預設
```
這樣解題就很快速了，不管他問的是多少區間和，只需要帶入function就可以
所以全部的程式碼看起來就像這樣：
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
cin >> n ;
vector<LL> pre(n+1) ;
pre[0] = 0 ;
for (int i=1;i<=n;i++) { // 計算前綴和
cin >> pre[i] ;
pre[i] += pre[i-1] ;
}
int q, l, r ;
cin >> q ;
for (int i=0;i<q;i++) { // 區間和
cin >> l >> r ;
cout << pre[r] - pre[l-1] << '\n' ;
}
return 0 ;
}
```
---
接下來就是延伸階段了，前綴和用在二維陣列的情況下
除了有左右找前綴和，還可以有上下找前綴和的變化
## 差分定義
相當於前綴和反過來，如果陣列 $A$ 的前綴和是 $B$，那 $A$ 同時是 $B$ 的差分
主要的用法是處理整個區間的操作，通常是高效率的加減運算
```cpp=
D[0] = A[0]
D[i] = A[i] - A[i-1] // i >= 2
```
接下來說明一下如何作區間加減法，我們可以先從前綴和的概念去思考，不過先說明最暴力的解法
假設我需要將 $A$ 中區間 `[L, R]` 都加 $5$，那程式碼會像是這樣
```cpp=
for (int i=L;i<=R;i++)
A[i] += 5 ;
```
如果需要 $m$ 次加減法操作，而陣列長度為 $n$，時間複雜度最糟就會到 $O(nm)$
這時候先回頭去看原本陣列改動後前綴和的改變，假設 `A[3] += 3`，更新後的前綴和也會跟著變化
這時候前綴和 `P[3] ~ P[n-1]` 都必須加上 $3$，換句話說，前綴和的區間 `[3, n-1]` 都加 $3$
這時候就很有趣了，因為原陣列的加法會變成前綴和陣列的區間加法，不過這個區間的結尾一定是 $n-1$
這時候我們考慮看看 `A[6] -= 3`，這時候前綴和 `P[6] ~ P[n-1]` 也都必須減去 $3$
也同樣是整個區間的減法，這樣一來一回，整個前綴和相較最開始，其實只有區間 `[3,6-1]` 有加 $3$
而區間 `[6, n-1]` 一加一減就抵銷了，前面我們說過對於前綴和陣列來說，原陣列其實是它的差分
換句話說，如果我們想要做原陣列的區間加法，應該去改動差分陣列，改動完後在回推新的陣列
區間減法也是同一個邏輯，所以這兩個操作其實就可以總結成下列公式
1. 區間加法: `D[L] += x, D[R+1] -= x` 之後做差分陣列的前綴和(更新後的原陣列)
2. 區間加法: `D[L] -= x, D[R+1] += x` 之後做差分陣列的前綴和(更新後的原陣列)
這樣在多個區間運算的情況下時間複雜度只有 $O(n+m)$
建立差分陣列、還原原陣列都是 $O(n)$，而區間操作每次 $O(1)$ 共改 $m$ 次所以是 $O(m)$
## 二維前綴和、差分
適用於二維陣列的計算方式，可以用於快速計算區域和或是快速做區域加減法，基本用法跟一維一樣
* `P[i][j]` 表示由四個點 $(0,0), (i,0), (0,j), (i,j)$ 圍成方形區域的區域和
所以要算 $(x1, y1)$ 作為左上，$(x2, y2)$ 作為右下的方形區域和
就要用 `P[x2][y2]-P[x1][y2]-P[x2][y1]+P[x1][y1]` 去算
整個二維前綴和實際的計算方法如下
```cpp=
// A: A[1][1] ~ A[n][m]
for (int i=0;i<=n;i++)
P[i][0] = 0 ;
for (int j=0;j<=m;j++)
P[0][j] = 0 ;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
P[i][j] = P[i-1][j] + P[i][j-1] + A[i][j] ;
// sum of x1, y1 -> x2, y2
cout << P[x2][y2]-P[x1][y2]-P[x2][y1]+P[x1][y1] << '\n' ;
```
二維差分的概念也一樣，我就不花時間去推了，直接給程式碼
```cpp=
// A: A[1][1] ~ A[n][m]
for (int i=0;i<=n;i++)
D[i][0] = 0 ;
for (int j=0;j<=m;j++)
D[0][j] = 0 ;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
D[i][j] = A[i][j] - A[i-1][j] - A[i][j-1] + A[i-1][j-1] ;
```
## d206. 00108 - Maximum Sum
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d206)
給你一個 $N\times N$ 的陣列，請你找出有最大和的子區域其和為多少
一個區域的和指的是該區域中所有元素值的和
一個區域是指相連的任意大小的子陣列
解析 :
二維的前綴和比較複雜，但是簡單來說就是取上取左然後刪除重疊區域
而子矩陣和也可以用前綴和算出，也是用刪上刪左補重疊的方式算出來
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int n ;
while (cin >> n) {
vector<int> tmp(n+1, 0) ;
vector<vector<int>> G(n+1, tmp) ;
int ans = 0 ;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
cin >> G[i][j] ;
G[i][j] += G[i-1][j] + G[i][j-1] - G[i-1][j-1] ; // 前綴和
// 子矩陣和
for (int x=1;x<=i;x++)
for (int y=1;y<=j;y++)
ans = max(ans, G[i][j] - G[i][y-1] - G[x-1][j] + G[x-1][y-1]) ;
}
}
cout << ans << '\n' ;
}
return 0 ;
}
```
Sign in with Wallet
Connect another wallet