# 【6-2】前綴和 & 後綴和

在以往的學習中，我們曾透過 `for` 迴圈來計算陣列中一段區間的元素總和

int sum = 0;
for (int i = L; i <= R; ++i) {
    sum += a[i];
}

* **時間複雜度**：每次都 $O(n)$

## 前綴和（Prefix Sum）

### 1. 定義
對長度為 `n` 的陣列 `a[0…n−1]`，建立 `prefix[]` 來儲存從開頭累加到每個位置的部分和：

$$
\text{prefix}[i] = \sum_{j=0}^{i} a_j
$$

vector<int> prefix(n);
prefix[0] = a[0];
for (int i = 1; i < n; ++i) {
    prefix[i] = prefix[i-1] + a[i];
}
// 範例：若 a = {5, 2, 4, 1, 3}
// 則 prefix = {5, 7, 11, 12, 15}

* **時間複雜度**：$O(n)$
### 2. 區間查詢

要算任意區間 `[L,R]` 的和，只要從 `prefix[R]` 扣掉不需要的前半段：

$$
\sum_{i=L}^{R} a_i =
\begin{cases}
\text{prefix}[R] - \text{prefix}[L-1], & L > 0,\\
\text{prefix}[R], & L = 0.
\end{cases}
$$

// 查 a = {5,2,4,1,3} 中 [1,3] 的和：2+4+1 = 7
int sumLR = (L > 0 ? prefix[R] - prefix[L-1] : prefix[R]);
// sumLR = prefix[3] - prefix[0] = 12 - 5 = 7

* **時間複雜度**：$O(1)$
---

## 後綴和（Suffix Sum）

### 1. 定義

如果我們想從某個位置一路加到陣列末尾，就用後綴和 `suffix[]`，其定義和前綴和對稱：

$$
\text{suffix}[i] = \sum_{j=i}^{n-1} a_j
$$

vector<int> suffix(n);
suffix[n-1] = a[n-1];
for (int i = n-2; i >= 0; --i) {
    suffix[i] = suffix[i+1] + a[i];
}
// 範例：若 a = {5, 2, 4, 1, 3}
// 則 suffix = {15, 10, 8, 4, 3}

* **時間複雜度**：$O(n)$
### 2. 區間查詢

要算任意區間 `[L,R]` 的和，只要從 `suffix[L]` 扣掉不需要的後半段：

$$
\sum_{j=L}^{R} a_j =
\begin{cases}
\text{suffix}[L] - \text{suffix}[R+1], & R+1 < n,\\
\text{suffix}[L], & R = n-1.
\end{cases}
$$

  // 查 a = {5,2,4,1,3} 中 [1,3] 的和：2+4+1 = 7
  int sumLR_suffix = (R+1 < n ? suffix[L] - suffix[R+1] : suffix[L]);
  // = suffix[1] - suffix[4] = 10 - 3 = 7

* **時間複雜度**：$O(1)$

---

當一個陣列需要多次計算區間總和時，利用前綴和和後綴和的技巧，可以有效降低複雜度，當然，如果只需要計算一次的話，就不需要這麼麻煩了（不過題目很少出現只要計算一次總和的）。

---

聯絡方式：[e-mail]
最後編修時間：2025/08/03 子柚筆