【演算法】差分（Differential Evolution）

簡介

陣列相鄰兩項的差值。時間複雜度從 $O(n)$ 降到 $O(1)$，好像也可以算是一種動態規劃。

用途

「快速」在區間 $[l, r]$ 加上 $X$ 值。

例 1（一維陣列）

假設我們要將一個一維陣列某段（index = 3~）都增加 5，也就是從這樣

0	0	0	0	0	0	0	0	0	0

變這樣

0	0	0	5	5	5	5	5	5	5

在差分的用法上這個陣列會變成這樣

0	0	0	5	0	0	0	0	0	0

好處非常明顯就是不用修改區間內全部的值，也就是不用做 n 次。
只需要改一個值，也就是只要做 1 次。

---

那假設我們只要 index = 3~6 改為 5，我們只要這樣做

0	0	0	5	0	0	0	-5	0	0

例 2（二為陣列）

原陣列：

0	0	0	0	0	0
0	5	5	5	0	0
0	5	5	5	0	0
0	5	5	5	0	0
0	0	0	0	0	0

差分陣列：

0	0	0	0	0	0
0	5	0	0	-5	0
0	0	0	0	0	0
0	0	0	0	0	0
0	-5	0	0	5	0

其原理為：

差分

0	0	0	0	0	0
0	d	0	0	-d	0
0	0	0	0	0	0
0	0	0	0	0	0
0	-d	0	0	d	0

實際數值

0	0	0	0	0	0
0	+d	+d	+d	0	0
0	+d	+d	+d	0	0
0	+d	+d	+d	0	0
0	0	0	0	0	0

差分 vs 前綴和

差分與前綴和的關係其實很微妙，它們互為反運算的關係。

就以 [0, 5, 5, 5, 0, 0] 為例

差分陣列：

0	5	0	0	-5	0

原陣列：

0	5	5	5	0	0

前綴和：

0	5	10	15	15	15

可以發現它們的關係是：

差分陣列的前綴 = 原陣列
原陣列的前綴 = 前綴和

前綴和的差分 = 原陣列
原陣列的差分 = 差分矩陣

題目

• ZeroJudge n565. 降雨量統計 (Rainfall)

參考資料

• TOI推廣線上練習賽歷屆試題