一、一維前綴和

1.1 定義

給定一個數組 a[1..n]，其前綴和數組 pre[1..n] 定義為：

$$pre[i]=a[1]+a[2]+?+a[i]$$

即 pre[i] 表示原數組從第 1 項到第 i 項的和。

1.2 構建

int a[N], pre[N];
for (int i = 1; i <= n; i++) 
{pre[i] = pre[i - 1] + a[i];
}

1.3 區間求和

使用前綴和可以在 $O(1)$ 時間內求任意區間 $[l,r]$ 的和：

$$sum=pre[r]?pre[l?1]$$

公式推導：

$$\begin{gathered} pre[r]=a[1]+a[2]+?+a[l?1]+a[l]+?+a[r] \\ pre[l?1]=a[1]+a[2]+?+a[l?1] \end{gathered}$$

所以兩者一減，剛好剩下區間 $[l,r]$ 的和。

1.4 應用場景

• 快速計算區間和
• 優化暴力 $O(n^2)$ 的區間統計問題為 $O(n)$

1.5 示例

// 輸入一個數組，求多個區間 [l, r] 的和
int a[N], pre[N];
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];while (q--) 
{int l, r;cin >> l >> r;cout << pre[r] - pre[l - 1] << '\n';
}

---

二、一維差分數組

2.1 定義

對于原數組 a[1..n]，其差分數組 diff[1..n] 定義為：

$$diff[i]=a[i]?a[i?1](i\ge 2),diff[1]=a[1]$$

2.2 構建

int a[N], diff[N];
diff[1] = a[1];
for (int i = 2; i <= n; i++) 
{diff[i] = a[i] - a[i - 1];
}

2.3 區間加法操作

若想對區間 $[l,r]$ 所有數加上 $d$，只需：

diff[l] += d;
diff[r + 1] -= d;

原理在于：差分數組記錄的是“增量”，只需要在區間起點加一個數、在區間終點的下一位減去這個數，就能確保中間所有位置都累加這個值。

然后通過前綴和還原整個數組：

a[1] = diff[1];
for (int i = 2; i <= n; i++) 
{a[i] = a[i - 1] + diff[i];
}

2.4 區間減法操作

若想對區間 $[l,r]$ 所有數減去 $d$，也可以使用差分數組：

diff[l] -= d;
diff[r + 1] += d;

原理類似：差分數組記錄的是“增量”，如果我們想對一個區間 $[l,r]$ 的所有元素減去 $d$，只需要在區間起點加上 $?d$，在區間終點的下一位加上 $+d$，就能確保整個區間內的值都減少 $d$，而其他位置不受影響。這與區間加法操作完全對稱，只是將 $d$ 替換為 $?d$。

---

三、差分原理

3.1 目的

差分數組的核心目的是：將原本需要 O(n) 的區間修改操作優化為 O(1)。

比如：我們想對數組中一段區間 $[l,r]$ 的所有元素都加上一個數 $d$，若用原數組暴力加法，每次操作就要 $O(r?l+1)$；當有 $m$ 次操作時，總復雜度是 $O(mn)$，會超時。

3.2 差分數組的構建

我們構建一個數組 $diff[1\dots n]$：

$$diff[i]=a[i]?a[i?1]$$

也可以理解為：

差分數組記錄的是原數組中相鄰兩項之間的“變化量”。

根據這個定義，有：

$$a[i]=diff[1]+diff[2]+?+diff[i]?a[i]=\sum _{j=1}^{i}diff[j]$$

也就是說，原數組可以通過差分數組做前綴和來還原。

3.3 差分操作的核心邏輯

想要將區間 $[l,r]$ 所有數都加上 $d$，我們可以在 diff[] 上做如下處理：

diff[l] += d;
diff[r + 1] -= d;

為什么這樣就能完成整個區間的加法？

我們回憶差分的“還原”過程：

a[1] = diff[1];
a[2] = a[1] + diff[2];
a[3] = a[2] + diff[3];
...

你會發現，前綴相加會讓 diff[l] 的影響一直傳導下去。直到 diff[r+1] 把這部分影響抵消為止。

也就是說：

• $a[l]$ 到 $a[r]$ 都被加上了 $d$
• 而 $a[r+1]$ 之后的數不受影響

這就實現了：O(1) 修改一個區間

---

四、一個形象的類比

假設你站在樓梯上，從第 1 級樓梯往上走，a[i] 是你在第 i 級臺階上的高度。

• 前綴和：相當于你每走一步都記一下總共走了多遠。
• 差分數組：相當于你記錄每一步你上升（或下降）了多少。

你只要知道每一步的變化量（差分數組），就能還原出每一級臺階的實際高度（原數組）；你也能知道在一段范圍內你升高了多少（前綴和）。

---

---

五、前綴和與差分的區別與聯系

類別	作用	技術本質	時間復雜度
前綴和	快速查詢區間和	把每個位置存成前綴累加和	查詢 $O(1)$，構建 $O(n)$
差分數組	快速區間修改	存儲相鄰值之間的“變化”	修改 $O(1)$，恢復 $O(n)$

它們的關系就像：

• 前綴和是累計的“總和”
• 差分是相鄰的“變化量”

差分數組其實就是前綴和的逆操作。

---

六、常見問題匯總

1. 差分數組的還原為什么用前綴和？

   差分數組記錄的是相鄰元素之間的增量，所以前綴和就是原數組。

2. 差分數組是否支持區間乘法？

   不支持，差分只能處理區間加減。

3. 差分數組是否可以從 0 開始？

   可以，但要注意下標對應的意義，最好從 1 開始更清晰。

4. 是否每次都需要重建差分數組？

   看情況。如果每次操作互不干擾，可以復用；否則建議重建或靜態開數組并清空。

---

七、總結

• 前綴和用于高效區間查詢
• 差分數組用于高效區間修改
• 兩者配合使用是處理“區間加減 + 查詢”類問題的利器

在處理數據量較大的題目（如 $10^5$ 或 $10^6$）時，前綴和與差分是比線段樹更快、更簡潔的選擇。