---
type: slide
slideOptions:
transition: fade;
---
<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
## Prefix Sum & Difference Array & Two Pointer
2024/11/06
----
* 前綴和
* 差分
* 雙指針
---
## 前綴和、差分
----
#### 一維前綴和
序列 $A_1, A_2,...,A_n$ 的長度為 $i$ 的前綴和記為 $S_i$ 而 $S_0$ =0，可以用來計算區間和。
$\sum\limits_{i = l}^r {A_i = S_r -S_{l-1}}$
可以簡單理解為前 $i$ 項的和，而求 $l\sim r$ 的區間和自然就是$S_r-S_{l-1}$
----
#### 二維前綴和
多維前綴和的構造方式與一維相同，主要是求區間和時要利用容斥原理
如何構造 矩陣 sum?
$sum_{r,c}=\sum\limits_{i = 1}^r \sum\limits_{j = 1}^c {arr_{i,j}}$
遞推求 sum 的過程為(容斥原理):
$sum_{i,j} = sum_{i-1,j} + sum_{i,j-1} - sum_{i-1,j-1} + arr_{i,j}$
----
### 如何應用
求子矩陣 ($r_1 , c_1$)~($r_2 , c_2$) 的和。
由遞推的算式可得 ($r_1 , c_1$)~($r_2 , c_2$) 的區間和為:
$ans = sum_{r_2,c_2} - sum_{r_1-1,c_2} - sum_{r_2,c_1-1} + sum_{r_1-1,c_1-1}$
----
圖例:
$sum_{r_2,c_2} - sum_{r_1-1,c_2} - sum_{r_2,c_1-1} + sum_{r_1-1,c_1-1}$
----
### 例題：
對一段長度為 $n$ 的區間，做出 $q$ 筆詢問
*詢問內容為區間和
* subtask 1: $n\cdot q \le 10^8$
* subtask 2: $n \le 10^2,\ q \le 10^8$
* subtask 3: $n \le 10^6,\ q \le 10^8$
----
### subtask 1: $n*q \le 10^8$
每次詢問就遍例一次，直接暴力加法
```cpp=
for(int i=1;i<=q;i++){
int l,r,ans=0;
cin>>l>>r;
for(int j=l;j<=r;j++){
ans+=arr[j];
}
cout<<ans<<"\n";
}
```
最差情況 : $q$ 次詢問都是求 $sum_{1,n}$
因此你每次都需要遍例 $1~n$，則時間複雜度為 $O(q\cdot n)$
----
### subtask 2: $n \le 10^2,\ q \le 10^8$
開 $10^2\cdot 10^2$ 的陣列，$sum[i][j]$ 紀錄 $i \sim j$ 的總和是多少
$q$ 筆詢問即可 $O(1)$ 解決掉 因此時間複雜度為 $O(n^2+q)$
----
### subtask 3: $n \le 10^6,\ q \le 10^8$
開 $10^6$ 的陣列， $sum[i]$ 紀錄 $i$ 的前綴和是多少
$q$ 筆詢問即可 $O(1)$ 解決掉 因此時間複雜度為 $O(n + q)$
```cpp=
int n,l,r,q;
int arr[N]={},sum[N]={};
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
sum[i]=sum[i-1]+arr[i];
}
cin>>q;
for(int i=1;i<=q;i++){
cin>>l>>r;
cout<<sum[r]-sum[l-1]<<"\n";
}
```
---
## 差分
----
### 差分的構造
差分是一種和前綴和相對的策略，可以當做是求和的逆運算。
$f_{i} = arr_{i} - arr_{i-1}$ , $f_{1} = arr_{1}$
```cpp=
ex:
arr[] = 1 10 5 -3 9
f[] = 1 9 -5 -8 12
```
同時不難發現，$arr_{i}$ 的值是 $f_{i}$ 的前綴和
----
## 計算區間和
若要利用 $f$ 計算 arr 的前綴和
$sum_{1,n} = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^i {f_j}=\sum\limits_{i = 1}^n (n-i+1)\cdot f_{i}$
## 以及修改區間值
若要在 $arr_l$ ~ $arr_r$ 都加上 $x$ 只需要修改 $f_l$ 和 $f_{r+1}$ 的值
```cpp=
f[l] += x;
f[r+1] -= x;
```
----
### 例題：
對一段長度為 $n$ 的區間，提出 $k$ 次區間修改後詢問你一次結果
* subtask 1: $n\cdot k \le 10^8$
* subtask 2: $n \le 10^6,k \le 10^8$
----
### subtask 1: $n\cdot k \le 10^8$
一樣直接暴力做，這邊就不贅述
----
### subtask 2: $n \le 10^6,\ k \le 10^8$
```cpp=
int n,l,r,k,x;
int arr[N]={},f[N]={};
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
f[i]=arr[i]-arr[i-1];
}
cin>>k;
for(int i=1;i<=k;i++){
cin>>l>>r>>x;
f[r+1]-=x,f[l]+=x;
}
```
---
前綴和是在非常多的題目都會用到的優化方式，也是一個簡單實用的技巧，請大家一定要時時刻刻想到前綴和。
另外 鑒於 xor 的性質(交換律)，xor 也可以拿來進行前綴和。
而差分雖然不常用到，但卻是針對某些題目時好用的工具。
---
## 雙指針 --- two pointers
雙指針顧名思義，就是同時使用兩個指針，在序列、串列結構上指向的是位置，在樹、圖等資料結構結構中指向的是節點，通過邊或同向移動，或相向移動來維護、計算要求的資訊。
通過快指針以及慢指針(左指針和右指針)的移動去限制可選擇的區塊。
----
### 頭尾固定的雙指針 --- sliding window
----
### 例題：[sliding windows maxmium](https://leetcode.com/problems/sliding-window-maximum/)
詢問每個大小為 $k$ 的 sliding windows (區間) 的最大值
$-10^4 \le a_i \le 10^4$
----
用 multiset 維護 sliding windows 內的數字
----
程式碼：
```cpp=
vector<int> ret;
multiset<int> st;
for(int i = 0; i < k; i++) {
st.insert(nums[i]);
}
ret.push_back(*(st.rbegin()));
for(int i = k; i < nums.size(); i++) {
st.insert(nums[i]);
st.erase(st.find(nums[i - k]));
ret.push_back(*(st.rbegin()));
}
return ret;
```
----
也可以丟進 priority_queue 裡面(存 pair(value,index))，
每次查找最大值，檢查 index 是否是符合條件的，
若不符合就 pop 掉直到找到就好。
----
### 例題：
給一個長度為 $n$、由非負整數組成的陣列 $a$，在 $\sum\limits^r_{i = l}a_i \le S$ 的情況下，最大化 $r - l$。
----
雙指針維護左界跟右界，被左界跟右界框起來的區域就是我們想要的，但是左界跟右界要怎麼移動呢？
----
每次將右界向右移動一格，並當總和超過 $S$ 時，將左界也向右移動。
----
$S = 20$，初始化時，沒有包含任何區間。
----
$l = 1, r = 1, sum \le 20, r++$
----
$l = 1, r = 2, sum \le 20, r++$
----
$l = 1, r = 3, sum \le 20, r++$
----
$l = 1, r = 4, sum \le 20, r++$
----
$l = 1, r = 5, sum > 20, l++$
----
$l = 2, r = 5, sum \le 20, r++$
----
$l = 2, r = 6, sum > 20, l++$
----
$l = 3, r = 6, sum > 20, l++$
----
$l = 4, r = 6, sum \le 20, r++$
----
$l = 4, r = 7, sum > 20, l++$
----
$l = 5, r = 7, sum > 20, l++$
----
結束了
----
$l$ 和 $r$ 最多只會移動 $n$ 步，複雜度 $O(n)$
----
程式碼：
```cpp=
for(int i = 0; i < n; i++) {
sum += arr[i];
while(sum > s) {
sum -= arr[l];
l++;
}
ans = max(ans, i - l + 1);
}
```
----
### 改變一下問題
給一個長度為 $n$、由非負整數組成的陣列 $a$
有幾組 pair $(l、r)$，符合 $\sum\limits^r_{i = l}a_i \le S$
----
再觀察一下上一題
對 $r = 4$ 來說， $l = 1, 2, 3, 4$ 都符合 $\sum\limits^r_{i = l}a_i \le S$
----
因此本題就是在上一題的基礎上，對每個右界計算有幾個左界可以符合條件。
----
程式碼：
```cpp=
for(int i = 0; i < n; i++) {
sum += arr[i];
while(sum > s) {
sum -= arr[l];
l++;
}
ans += (i - l + 1);
}
```
----
遇到一個問題時，如果他是要求最好的區間或者是有幾個區間符合條件時，就可以考慮雙指針，至於指針要放哪，就要看題目而定了。
----
### 例題：[Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
給一個為 $n$ 的陣列 $arr$
$a_i$ 代表在 $x = i$ 的位置有高度為 $a_i$ 的垂直線，
選兩個位置 $i、j$ 且 $i < j$，計算 $\text{min}(a_i, a_j)\times (j - i)$ 的最大值
----
### 做法二：
一開始先將指針放在最左邊跟最右邊，並比較兩邊的值，將值較小的指針往中間移，因為對這個指針來說，另外一邊的指針移動對答案是沒有貢獻的
----
### 程式碼：
```cpp=
int maxa = 0;
int l = 0, r = n - 1;
while(l < r) {
maxa = max(maxa, (r - l) * min(arr[l], arr[r]));
if(arr[l] < arr[r]) {
l++;
}
else r--;
}
```
---
## 練習 & 問問題時間
### [作業網址](https://vjudge.net/contest/669014)
Google Drive
Gist
Clipboard
Sign in with Wallet
