---
tags: 技巧
---

# 前綴和
所謂前綴和是指一個數列的所有前項和
舉例來說
今有一個陣列

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

那麼這個數列的前綴和即為

int pre[10] = {1, 3, 6, 10, 15, 21, 28, 36, 45, 55};

|索引值|0|1|2|3|4|5|6|7|8|9|
|-|-|-|-|-|-|-|-|-|-|-|
|原數列(arr)|1|2|3|4|5|6|7|8|9|10|
|前綴和(pre)|1|3|6|10|15|21|28|36|45|55|

也就是說第 $n$ 項的前綴和就是第 $n-1$ 項的前綴和加上數列第 $n$ 項
$$p_n = p_{n-1}+a_n$$
## 為什麼要用前綴和
在計算區間和時能達到時間複雜度 $O(1)$
以上面的範例來說明
如果想知道數列中第$2$項到第$7$項的和,只要計算前綴和 $p_7 - p_1$

數列中第$i$到第$k$項計算方法

$$sum(a_i, a_k) = p_k - p_{i-1}$$

## 注意

為避免索引值與數列索引之混淆且便於前綴計算
前綴和的陣列會從索引值1開始計算, 索引值0預設為0

---
{%hackmd @hlc23/dark-theme %}