# 前綴和
> 上一篇文章 [排序](https://hackmd.io/AbLO_6vkTiq63tKrp-L7_w)
> 下一篇文章 [圖論基礎觀念](https://hackmd.io/CbclZG4dSyuVAtq1YOEt8A)
> 先備知識 無
> 延伸閱讀 [2D Prefix Sum and Submatrix Sum Queries](https://youtu.be/WibxoqMSMCw?si=oKBgHOQsBySHAvoO)
---
## <font size=6>前言</font></br>
<!-- 想要算出一個區間的和大小 -->
大家都知道，財務管理是很重要的吧!如果不好好管理自己的收支，不小心就會面臨財務危機，跟只剩下一張帥臉的統神一起端火鍋(沒想到學個演算法還會被老梗釣魚吧)。
當你想要知道一年當中哪段時間你花了多少錢時，你會需要把那段時間每個禮拜的花錢都加總幾來。這聽起來應該不太花時間，反正一年也沒多少個禮拜吧!可是如果今天是算公司財報，就可能會有非常多的部門花的錢要一起算，你慢慢算不知道要花多少時間，因此就需要用到**前綴和**的概念了。
## <font size=6>前綴和定義與作用</font></br>
### 前綴和定義
前綴和是甚麼呢?你國中時應該學過累積長條圖吧!前綴和在做的事就是累積長條圖在做的事情。在計算從第`1`筆資料累積到第`i`筆資料加總是多少。
| **每筆數值的長條圖** | **轉換成累積長條圖** |
| -------- | -------- |
| | |
給定一個陣列叫做 `arr` 其對應前綴和叫做 `prefix_sum`:
```python=
arr = [5,2,3,5,3]
prefix_sum = [0]*(len(arr)+1)
prefix_sum[0] = 0 #當 arr 中還沒加入元素時，總和理所當然是 0
for i in range(0,len(arr)):
prefix_sum[i+1] += prefix_sum[i]+arr[i]
print("sum = ",prefix_sum)
```
**Output |** `sum = [0,5,7,10,15,18]`
### 求區間總和
當你要求 `arr` 中 `arr[2:5]` 區間的總和，直接將 `prefix_sum[5]` - `prefix_sum[2]` 就能得到了。
在這個舉例中，原本需要花 3 次的時間，變成只要花上 1 次。如果想要求區間大小為 `k` 的總和，原本會需要花上 `O(k)` 的時間，但現在只要 `O(1)`。
## <font size=6>程式實作</font></br>
那我在這邊帶一個範例讓你看看有沒有使合前綴和的差別。
### 範例
> 給定一個長度為 `n` 的整數陣列，找出所有區間和為 `x` 的區間有多少個。
>> **Input**
>> 第一行有兩個數字，分別為 `n` 與 `x`
>> 第二行有 `n` 個數字，為整數陣列的所有 element， `a1,a2,...,an`
>
>> **Output**
>> 區間和為 `x` 的區間數量
>
> **測資範圍**
> \begin{gather*}
> 1 \le n \le 2 \cdot 10^5 \\ -10^9 \le x,a^{}_{i} \le 10^9
> \end{gather*}
> **Example**
>> **Input**
>> ```
>> 5 7
>> 2 -1 3 5 -2
>> ```
>
>> **Output**
>> ```
>> 2
>> ```
### 窮舉法
:::danger
這題的窮舉法就是把所有可能的區間都列出來，然後再去判斷它們的值是否等於 `x`
### 程式碼
```python=
n, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(n): # i 為區間的開頭
total = 0
for j in range(i, n): ＃ｊ為區間的結尾
total += a[j]
if total == x: #計算此區間是否符合目標值 x
count += 1
print(count)
```
### 時間複雜度
從迴圈來判斷，可以很直觀的知道其時間複雜度為 `O(n^2)`
:::spoiler **程式碼解釋**(點我展開)
透過兩層迴圈，枚舉所有可能的子陣列，並計算其總和是否等於目標值 `x`
外迴圈的 `i` 代表區間開頭，內迴圈的 `j` 代表區間結尾
`count` 用以計算此區間是否符合目標值 `x`
:::
### 前綴和
:::success
利用前綴和來計算是否有區間大小符合 x 。對於一個 prefix sum `sumi`，我需要找到一個 `sumt` 使得 `sumi - sumt = x`，轉換一下這個等式，當我要看有沒有配合 `sumi`的 prefix sum 時，我需要知道是否存在 `sumt`會等於`sumi - x`。
### 動畫
### 程式碼
```python=
from collections import defaultdict
n, x = map(int, input().split())
a = list(map(int, input().split())) #陣列
# Initialization
prefix_counts = defaultdict(int) #紀錄每種 prefix sum 有多少個
prefix_sum = 0
prefix_counts[prefix_sum]+=1
count = 0
#Iteration
for num in a:
prefix_sum += num
#為避sumi與sumt, i<t,所以需要在找完`prefix_sum-x` 後才會把`prefix sum`加入dictionary
count += prefix_counts[prefix_sum - x]
prefix_counts[prefix_sum] += 1
print(count)
```
### 時間複雜度
```python=13
for num in a:
prefix_sum += num
#為避sumi與sumt, i<t,所以需要在找完`prefix_sum-x` 後才會把`prefix sum`加入dictionary
count += prefix_counts[prefix_sum - x]
prefix_counts[prefix_sum] += 1
```
在迴圈當中的操作只有增加 `prefix_sum` 的數值以及對於 `prefix_counts` 這個 dict 增加元素或修改元素的 value。這些操作都是 `O(1)`
**所以最後得到時間複雜度為 `O(n)`**
:::spoiler **程式碼解釋**(點我展開)
#### 第七行
```python=7
prefix_counts = defaultdict(int)
```
將 `prefix_counts` 型別設置為 **dict**，並且會引發下面敘述的效果
> 當你嘗試存取一個不存在的鍵（key）時，它不會引發 KeyError，而是自動為該鍵建立一個預設值。在這裡，預設值是整數 0，因為 int() 回傳的是 0
> ```python=9
> prefix_counts[prefix_sum]+=1
> ```
> 在這行指令執行以前 ， 0 還不存`prefix_counts` 當中，因此這行指令執行前，會先執行 `prefix_counts[prefix_sum] = 0`
#### prefix_sum
記錄目前的前綴和，在迴圈當中慢慢累加，一開始的數值為 0。(第 8 行)
#### prefix_counts
1. 記錄每一種前綴總和出現的次數，一開始只有 0 這個 `prefix_sum`，而且只有 1 個 0。(第 9 行)
2. 第 17 行指令就是把當前的 `prefix_sum` 記錄下來。
> * 假設目前 `prefix_counts[prefix_sum]` 的數值為 10，加上 1 後就會變成 11
#### 整體步驟
1. 初始化 `prefix_counts[0] = 1`代表一開始只有 0 這個 `prefix_sum`，而且只有一個。
2. 遍歷陣列，對於每個元素
> * 更新 `prefix_sum`。
> * 檢查 `prefix_counts[prefix_sum - x]` 是否存在，若存在，將其值加到計數器 `count`。
> * 將當前的 `prefix_sum` 加入 `prefix_counts` 中，並更新其出現次數。
:::
<!-- 總結一下兩種方式的時間複雜度 -->
## <font size=6>時間複雜度比較</font></br>
假設題目給定 `n = 10^5`，OJ 時間限制給你 `10s` ，也就是說只能跑 `10^7`行程式。
| 方法 | 時間複雜度 | 程式運行行數 | 超時 |
| ------ | ------------ | ------------ | ------ |
| 窮舉法 | $$ O(n^2) $$ | `10^10` | 超時 |
| 前綴和 | $$ O(n) $$ | `10^5` | 沒超時 |
可以看到窮舉法跟前綴合的差距了吧!這就是差距啦!看到沒!
<!-- 給題單讓他們試試(競程vjudge) -->
## <font size=6>前綴和的題目</font></br>
- CSES 1661
- CSES 1662
- CodeForces 1398C
- CodeForces 1826D
- CodeForces 835C (沒有頭緒的話可以參考這裡 [《2D Prefix Sum and Submatrix Sum Queries》](https://youtu.be/WibxoqMSMCw?si=oKBgHOQsBySHAvoO))
---
> 上一篇文章 [排序](https://hackmd.io/AbLO_6vkTiq63tKrp-L7_w)
> 下一篇文章 [圖論基礎觀念](https://hackmd.io/CbclZG4dSyuVAtq1YOEt8A)
> 先備知識 無
> 延伸閱讀 [2D Prefix Sum and Submatrix Sum Queries](https://youtu.be/WibxoqMSMCw?si=oKBgHOQsBySHAvoO)
> 觀念是非題 [簡單演算法觀念是非題](https://docs.google.com/forms/d/e/1FAIpQLSdd_t0jHeIXB8fM9935wXLdO5CUGxpOceAgYPbQ_iUu601Qcg/viewform?usp=header)
Sign in with Wallet
Connect another wallet