一、定義：

差分，又名差分函數或差分運算，差分的結果反映了離散量之間的一種變化。

例如，我們有一段離散化序列：a[1],a[2],a[3]......a[n-1],a[n], 我們可以建立數列的每一項與前一項的差值數組 c，

則有 c [1] = a[1] - a[0]，當 i>=2 時有 c[i]=a[i]-a[i-1]。這樣我們就可以將一段序列的差值序列記錄下來。

?

二、性質：

先來看這樣的例子：

我們可以發現：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a[1] = c[1]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a[2]=c[1]+c[2]=a[1]+a[2]-a[1]=a[2]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?.......

我們可以發現原數列的第 i 項可以由差分數組前 i 項和得到，也就是 差分數組的前綴和。

如果我們求原數列的前i項和，就是差分數組的前綴和的前綴和。

列出公式有：

?

三、應用：

1、快速的區間加減操作：

對一段區間 [ L ,R] 進行加 x 的操作該怎樣進行呢，我們知道 c 數組存儲的是每一項與前一項的差值，一段區間全部加x，那么區間內的差值應該保持不變，需要改變的只是兩個端點， 也就是 c[ L?] 和 c[ R+1]項。c[ L]比前一項多 x，所以有c[L ] += x，c[R]也增加x，其后一項 c[ R+1] 減少 x，則 c [R+1] -= x 。

因此我們在處理一段區間時可以直接對受影響的兩個值進行操作即可，簡單快速。

2、區間求和、求單點值：

如上面的公式：單點和為差分數組的前綴和，區間和為差分數組前綴和的前綴和。

3、樹狀數組中的差分應用：

這個大佬寫的很好，這里不再過多贅述。

https://www.cnblogs.com/kickit/p/9172189.html

?

四、例題：

1、HDU1556--Color the ball ??https://vjudge.net/problem/HDU-1556

2、POJ--3263--????Tallest Cow ??https://vjudge.net/problem/POJ-3263

3、[ NOIP2012提高 & 洛谷P1083] ?借教室 ? ?https://www.luogu.org/problem/P1083

4、二維差分：HDU-6514 ?Monitor???https://vjudge.net/problem/HDU-6514

關于這個題，有大佬寫的賊棒：https://blog.csdn.net/D5__J9/article/details/89428614

?

青山遮不住，畢竟東流去。 江晚正愁余，山深問鷓鴣。

刀刃飛，誰可為我敵。衣袂舞，一笑常門寂，而幸相遇，風清月明。

致QDU美好的夜景。

?

總結

以上是生活随笔為你收集整理的差分数组分析详解+例题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。