【C++】競程筆記（前綴和、差分）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
前綴和（Prefix-sum）
---
要快速計算某區間的和，會用到前綴和。
Image Source：https://osgoodgunawan.medium.com/prefix-sum-80d531154b95
依照上圖，A 為原始序列，P 為前綴和序列，則前綴和用程式寫就是：
完整一點：
```cpp=
vector<int> P(n + 1, 0); // P[0] = 0
for (int i = 0; i < n; ++i) {
P[i + 1] = P[i] + A[i];
}
```
我們可以利用前綴和計算區間 $[L, R]$ 的總和，可於 $O(1)$ 時間內完成，但在準備前綴和序列的時間複雜度是 $O(n)$ 。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {2, 4, 5, 7, 1, 3}; // 原始序列
int n = nums.size();
// 建立前綴和序列
vector<int> prefix(n + 1, 0); // prefix[0] = 0
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
int L = 1, R = 4; // 計算區間 [L, R] 的總和
int rangeSum = prefix[R + 1] - prefix[L];
cout << "區間 [" << L << ", " << R << "] 的總和是：" << rangeSum << endl;
return 0;
}
```
輸出：
```
區間 [1, 4] 的總和是：17
```
### 例題 1
---
例題：https://cses.fi/problemset/task/1643
講到 Maximum Subarray Problem（最大子陣列問題），就要講到 Kadane's Algorithm。
Kadane's Algorithm 是專門用來找出一維數字陣列中總和最大的連續子陣列的演算法，日後在解決 DP（Dynamic Programming） 上的題目會常用到這個。
:::success
子陣列（subarray）：是指一個陣列中由連續元素所構成的區間。區間可從原陣列中的任意起點開始，也可從任意位置結束。
如：`int arr[] = {1,2,3,4};` 為原始陣列，則其 subarray 可為：
* 長度為 1 的：`{1}, {2}, {3}, {4}`
* 長度為 2 的：`{1, 2}, {2, 3}, {3, 4}`
* 長度為 3 的：`{1, 2, 3}, {2, 3, 4}`
* 長度為 4 的：`{1, 2, 3, 4}`
若不連續的組合如：`{1, 3}`、`{2, 4}` 就稱為子序列（subsequence）
:::
而 Kadane's Algorithm 的演算流程如下：
1. 通常有兩個變數：
`currentSum`：目前子陣列總和。
`maxSum`：目前找到的最大子陣列總和。
以上初始值都設為陣列中的第一個元素（即 index = 0）。
2. 遍歷陣列：
從第二個元素開始，而每次走到一個位置的時候，都要問自己是要繼續前面的總和還是在這裡重來？計算方式如：
```cpp
currentSum = max(現在的元素, currentSum + 現在的元素);
```
現在的元素從第二個元素（假設 `arr[1]`）開始，假設 `arr[1] = 3`、`arr[0] = -1`、`currentSum = arr[0]`，那經過 max 之後，他就會繼續前面的總和，變成 `currentSum = 3`。
3. 更新最大總和：
如果 currentSum 比 maxSum 還大，就更新 maxSum：
```cpp
maxSum = max(maxSum, currentSum);
```
延續上面的例子，確實 currentSum 比較大，就直接更新。
最後整個迴圈遍歷完後，就可以得到最大子陣列總和了。
回到最開始的例題，於是我們可以用這個演算法去做這題了：
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
long long max_sum = arr[0];
long long current_sum = arr[0];
for (int i = 1; i < n; ++i) {
current_sum = max(arr[i], current_sum + arr[i]);
max_sum = max(max_sum, current_sum);
}
cout << max_sum << "\n";
return 0;
}
```
那你說這跟前綴和有啥屁關係？其實也是可以用前綴和解，只是要將問題稍微轉個角度想：要找出兩個位置 `i < j`，使得 `prefix[j] - prefix[i]` 最大。
以下的程式碼中，`ans = max(ans, s - mn);` 的 `s - mn` 就是 `prefix[j] - prefix[i]`。
```cpp=
// from NTUCPC Guide
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
ll s = 0;
ll mn = 0;
ll ans = -LLONG_MAX;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
s += x;
ans = max(ans, s - mn);
mn = min(mn, s);
}
cout << ans << "\n";
}
```
二維前綴和（2D-Prefix Sum）
---
給定一個大小為 `m × n` 的二維陣列（矩陣）A，並建立一個矩陣 P，使 `P[i][j]` 代表從 `(0,0)` 到 `(i,j)` 的子矩陣內所有元素的總和。
公式：
$$P[i][j]=A[i][j]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]$$
要查詢任意一個矩形區域的總和時（如從 `(x1, y1)` 到 `(x2, y2)`），只需透過簡單的四個查詢值即可：
$$Sum(x1,y1,x2,y2)=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]$$
那這樣可以先用 $O(n^{2})$ 時間算出 2D 前綴和，用 $O(1)$ 就可以求出矩形區域的和了。
來舉例一下（Python Code，因為 C++ 陣列寫起來比較麻煩）：
假設有 3x3 矩陣：
```python=
A = [ [1, 2, 3],
[4, 5, 6],
[7, 8, 9] ]
```
要建立一個 2D 前綴矩陣：
```python=
P = [ [1, 3, 6],
[5, 12, 21],
[12,27, 45] ]
```
以下是 A 的矩陣示意圖：
前綴和矩陣的 `P[0][0] = 1` 沒毛病，再來講講 `P[1][1] = 12`，其實他就是 A 裡面的 1, 2, 4, 5 做相加得出的結果，也就是以下那四塊矩形的面積（位置從矩陣 A `(0, 0)` 到 `(1, 1)`）。
以此類推，`P[2][1] = 27` 就是從原始矩陣 A 的位置 `(0, 0)` 到 `(2, 1)` 對 A 的 1, 2, 4, 5, 7, 8 等數字做相加，如下圖紅色區塊所示：
接下來若要求取某段區間內的矩形範圍總和，則如下所示：
若我們不是要從 `(0, 0)` 出發，而是從 `(1, 1)` 出發，到 `(2, 2)` 結束呢？（某段區間求和）則用到上方的 Sum 公式：
$$Sum=P[2][2]−P[0][2]−P[2][0]+P[0][0]=45−6−12+1=28$$
畫圖的方式就如下所示：
我們要求得右下角四塊矩形面積（在 A 矩陣中就是 5, 6, 8, 9），就會做如上圖的運算，由於因為面積為 1 的矩形被扣掉兩次，所以要給他補一次回來。
### 例題 2
---
例題（Zerojudge）a694. 吞食天地二：https://zerojudge.tw/ShowProblem?problemid=a694
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
while (cin >> n >> m) {
vector<vector<int>> grid(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> grid[i][j];
}
}
vector<vector<int>> p(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + grid[i][j];
}
}
for (int i = 0; i < m; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int sum = p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1];
cout << sum << "\n";
}
}
return 0;
}
```
基本上就是套上面給的公式：
$$P[i][j]=A[i][j]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]$$
$$Sum(x1,y1,x2,y2)=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]$$
然後稍微注意一下輸出輸入優化，並且注意輸入前綴和的部分，for 迴圈初始值是 `int i = 1`。
差分（Difference）
---
簡單來說就是陣列中相鄰兩項元素的差值。
給定一個數列 `A[1...n]`，我們可以定義它的差分陣列 `D[1...n]` 為：
$$D[i]=A[i]−A[i−1]$$ （ $A[0] = 0$ 或依照情況定義）
若知道所有的差，也就是差分陣列 D 的每一項，就可以透過相加差分陣列的第 i 項去求得原始陣列 A 的第 i 項：
$$A[i]=D[1]+D[2]+\cdots+D[i]$$
而這其實就是在做「前綴和」，因為差分是「變化量」，只要把變化量一項項累加回去，就可以得到原來的數列。
該公式可用 sigma 代號直接簡化：
$$A[i] = \sum_{k=1}^{i}D[k]$$
那差分是拿來幹嘛的呢？是拿來做快速區間加法用的。
當我們想對某個區間 $[l, r]$ 都加上一個值 $x$ 時，如果直接修改每一個 $A[i]$ ，時間複雜度是 $O(r - l + 1)$ 。
若用差分陣列，僅需做到以下操作即可：
```cpp=
D[l] += x
D[r+1] -= x
```
做完以上操作後，對 D 做前綴和（還原陣列 A），就會發現 $[l, r]$ 區間都被加了 $x$ ，其餘區間不變。
以下是個 C++ 差分範例：
```cpp=
#include <iostream>
#include <vector>
using namespace std;
// 建立差分陣列
void difference_array(const vector<int>& A, vector<int>& D) {
int n = A.size();
D[0] = A[0];
for (int i = 1; i < n; ++i) {
D[i] = A[i] - A[i - 1];
}
}
// 區間加值：對 [l, r] 區間加上 val
void range_add(vector<int>& D, int l, int r, int val) {
D[l] += val;
if (r + 1 < D.size()) {
D[r + 1] -= val;
}
}
// 還原原始陣列 A（前綴和）
void restore_array(const vector<int>& D, vector<int>& A) {
int n = D.size();
A[0] = D[0];
for (int i = 1; i < n; ++i) {
A[i] = A[i - 1] + D[i];
}
}
int main() {
// 建立原始陣列
vector<int> A = {0, 0, 0, 0, 0};
int n = A.size();
// 建立差分陣列
vector<int> D(n);
difference_array(A, D);
// 區間更新操作
range_add(D, 1, 3, 5); // 對第 2~4 項加上 5
range_add(D, 2, 4, 2); // 對第 3~5 項加上 2
// 還原陣列
restore_array(D, A);
cout << "A : ";
for (int i = 0; i < n; ++i) {
cout << A[i] << " ";
}
cout << "\n";
return 0;
}
```
輸出結果：
```
A : 0 5 7 7 2
```
### 例題 3
---
例題（Zerojudge e340. 差分練習）：https://zerojudge.tw/ShowProblem?problemid=e340
這題很簡單，只要求差分陣列即可。
B 為原始陣列，A 為差分陣列。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> B(N);
for (int i = 0; i < N; i++) {
cin >> B[i];
}
vector<long long> A(N);
A[0] = B[0];
for (int i = 1; i < N; i++) {
A[i] = B[i] - B[i-1];
}
for (int i = 0; i < N; i++) {
cout << A[i] << " ";
}
return 0;
}
```
### 例題 4
---
2021 年 11 月 APCS 第三題。
例題（Zerojudge g597. 3. 生產線）：https://zerojudge.tw/ShowProblem?problemid=g597
這題結合的演算法蠻多的，貪心法、前綴和、差分、排序都有。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
// 差分用於計算每個位置的工作量
vector<long long> diff(n, 0);
for (int i = 0; i < m; i++) {
int l, r, w;
cin >> l >> r >> w;
l--; r--; // 因為題目數字範圍關係, 為了要符合 C++ 索引規範把它 - 1
// 以下部分是差分的區間加值運算
diff[l] += w;
if (r + 1 < n) diff[r + 1] -= w;
}
// 前綴和用於計算每個位置的總工作量
// 這邊就是如同本文中提到的還原陣列的操作, 也是前綴和的操作
vector<long long> sum_w(n, 0);
sum_w[0] = diff[0];
for (int j = 1; j < n; j++) {
sum_w[j] = sum_w[j - 1] + diff[j];
}
vector<long long> t(n);
for (int i = 0; i < n; i++) {
cin >> t[i];
}
// 排序工作量（由大到小排序）
sort(sum_w.rbegin(), sum_w.rend());
// 用反向迭代器, 就只是加個 r, 就可以達成降序的效果
sort(t.begin(), t.end());
long long total = 0;
for (int i = 0; i < n; i++) {
total += t[i] * sum_w[i]; // 計算最小時間花費總和
}
cout << total;
return 0;
}
```
總結
---
### 一、前綴和（Prefix Sum）
#### 概念：
前綴和是一種預處理技巧，可於 $O(1)$ 時間內查詢任意區間 $[L, R]$ 的和。
#### 一維前綴和：
```cpp=
vector<int> P(n + 1, 0);
for (int i = 0; i < n; ++i)
P[i + 1] = P[i] + A[i];
```
#### 查詢任意區間 $[L, R]$ 的和
```cpp=
sum = P[R + 1] - P[L];
```
---
### 二、二維前綴和（2D Prefix Sum）
#### 概念：
用於矩陣中的子區域總和的查詢。
#### 預處理公式：
$$P[i][j]=A[i][j]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]$$
#### 查詢子矩陣 $(x1, y1)$ 到 $(x2, y2)$ 總和公式：
$$Sum=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]$$
---
### 三、差分（Difference）
#### 概念：
差分是相鄰元素的變化量，可做快速區間加值，之後再還原成原始陣列。
#### 差分公式：
$$D[i]=A[i]−A[i−1](A[0]=0)$$
#### 快速區間加值：
```cpp=
D[l] += x;
D[r + 1] -= x;
```
對差分陣列做前綴和即可還原 A。
---
### 比較表
| 演算法 | 功能 | 預處理複雜度 | 查詢複雜度 | 應用 |
| ----- | ---------- | ---------- | ------------------------- | -------------- |
| 前綴和 | 快速查詢區間總和 | $O(n)$ | $O(1)$ | 陣列區間查詢、DP 優化 |
| 二維前綴和 | 快速查詢矩形區域總和 | $O(n^{2})$ | $O(1)$ | 影像處理、即時地圖 |
| 差分陣列 | 快速區間加法 | $O(n)$ | $O(1)$（還原陣列為 $O(n)$） | 線段更新 |
Sign in with Wallet
Connect another wallet