差分和前綴和的原理、用法和區別。

前綴和（Prefix Sum）

核心思想：預處理數組的前綴和，快速回答「區間和查詢」
適用場景：數組靜態（更新少、查詢多），需要頻繁計算任意區間的和

1. 定義與構建

對于原數組 ?a[0...n-1]?，前綴和數組 ?preSum??滿足：
preSum[i] = a[0] + a[1] + ... + a[i-1]?
（?preSum[0] = 0?，方便邊界計算）

構建代碼：

vector<long long> buildPreSum(vector<int>& a) {
int n = a.size();
vector<long long> preSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + a[i];
}
return preSum;
}

2. 核心作用：O(1) 區間和查詢

原數組區間 ?[l, r]?（閉區間）的和為：
sum(l, r) = preSum[r + 1] - preSum[l]?

示例：
原數組 ?a = [1, 2, 3, 4]?，則 ?preSum = [0, 1, 3, 6, 10]?
查詢 ?a[1..3]?（元素 ?2,3,4?）的和：?preSum[4] - preSum[1] = 10 - 1 = 9?

差分（Difference Array）

核心思想：預處理差分數組，快速執行「區間更新」
適用場景：數組動態（更新多、查詢少），需要頻繁對區間進行加減操作

1. 定義與構建對于原數組 ?

a[0...n-1]?，差分數組 ?diff??滿足：
diff[i] = \begin{cases}?
a[0] & (i=0) \\
a[i] - a[i-1] & (i>0)?
\end{cases}?

構建代碼（直接初始化，或從原數組推導）：

vector<int> buildDiff(vector<int>& a) {
int n = a.size();
vector<int> diff(n, 0);
diff[0] = a[0];
for (int i = 1; i < n; ++i) {
diff[i] = a[i] - a[i-1];
}
return diff;
}

2. 核心操作：O(1) 區間更新

對原數組 ?a??的區間 ?[l, r]??全部加 ?val?，只需操作差分數組：

diff[l] += val; ? ? ? ? ? // 起點 l 開始有增量
if (r + 1 < n) {
diff[r + 1] -= val; ? // 終點 r+1 處取消增量（防止擴散到區間外）
}


原理：差分數組記錄的是「相鄰元素的變化量」。當通過前綴和還原原數組時，?diff[l] += val??的影響會傳遞到 ?a[l..n-1]?，而 ?diff[r+1] -= val??會抵消 ?r+1??之后的影響，最終只有 ?a[l..r]??被加上 ?val?。

3. 還原原數組（從差分 → 原數組）

對差分數組求前綴和，即可還原原數組：

vector<int> restoreArray(vector<int>& diff) {
int n = diff.size();
vector<int> a(n, 0);
a[0] = diff[0];
for (int i = 1; i < n; ++i) {
a[i] = a[i-1] + diff[i];
}
return a;
}

或更高效的原地操作（差分數組直接變原數組）：

for (int i = 1; i < n; ++i) {
diff[i] += diff[i-1];
}
// 此時 diff 數組等價于原數組 a

前綴和 vs 差分：核心區別?

特性 前綴和（Prefix Sum） 差分（Difference Array）?
核心用途 快速查詢區間和（靜態數組） 快速執行區間更新（動態數組）?
操作對象 原數組 → 前綴和數組（預處理） 原數組 → 差分數組（預處理）?
時間復雜度 構建 O(n)，查詢 O(1) 構建 O(n)，區間更新 O(1)，還原 O(n)?
典型場景 數組不變，頻繁查區間和（如 LeetCode 560） 數組常變，頻繁對區間加減（如 LeetCode 1109）?

綜合示例：前綴和 + 差分

題目：

1.?初始數組 ?a = [1, 2, 3, 4]?
2.?對區間 ?[1, 3]?（元素 ?2,3,4?）加 ?5?
3.?查詢最終數組的區間 ?[0, 2]?（元素 ?1,7,8?）的和

步驟 1：用差分執行區間更新

原數組 ?a = [1, 2, 3, 4]?，構建差分數組：

diff = [1, 1, 1, 1] ?// 因為 2-1=1, 3-2=1, 4-3=1


對區間 ?[1, 3]??加 ?5?：

diff[1] += 5; ? // diff[1] = 6
if (3+1 < 4) diff[4] -=5; ?// 數組長度 4，r+1=4 越界，無需操作


此時差分數組 ?diff = [1, 6, 1, 1]?

步驟 2：還原原數組（差分 → 原數組）

對 ?diff??求前綴和：

a[0] = 1 ?
a[1] = 1 + 6 = 7 ?
a[2] = 7 + 1 = 8 ?
a[3] = 8 + 1 = 9 ?


還原后數組 ?a = [1, 7, 8, 9]?

步驟 3：用前綴和查詢區間和

構建前綴和數組 ?preSum?：

preSum = [0, 1, 8, 16, 25] ?


查詢區間 ?[0, 2]??的和：

sum = preSum[3] - preSum[0] = 16 - 0 = 16

總結

- 前綴和是「區間和查詢」的優化工具，適合數組靜態、查詢頻繁的場景。
- 差分是「區間更新」的優化工具，適合數組動態、更新頻繁的場景。
- 兩者常配合使用：用差分處理更新，再用前綴和處理查詢，覆蓋更復雜的需求。

理解這兩個技巧的核心邏輯后，很多數組操作的題目（尤其是競賽題）都能迎刃而解。