差分?jǐn)?shù)組

定義

百度百科中的差分定義
//其實(shí)這完全和要講的沒關(guān)系 qwq

進(jìn)去看了之后是不是覺得看不懂？

那我簡(jiǎn)單概括一下qwq

差分?jǐn)?shù)組de定義：記錄當(dāng)前位置的數(shù)與上一位置的數(shù)的差值.

栗子

容易發(fā)現(xiàn)的是,\(\sum_{j=1}^{i} b_j\)即代表\(a_i\) 的值. \((\sum\) 即代表累加.)

思想

看到前面的\(\sum\) 你一定會(huì)發(fā)現(xiàn)這是前綴和!

那你認(rèn)為這是前綴和? 的確是qwq.

實(shí)際上這并不是真正意義上的前綴和.

前綴和的思想是 根據(jù)元素與元素之間的并集關(guān)系(和的關(guān)系),求出某些元素的和的值.對(duì)應(yīng)的為$\sum_{j=1}^{i} a_j $

而差分的思想與此不同.

差分的思想是 根據(jù)元素與元素之間的邏輯關(guān)系(大小關(guān)系),求出某一位置元素的值.對(duì)應(yīng)的為\(\sum_{j=1}^{i} b_j\)

What?不懂?看下面

繼續(xù)撿起剛剛的栗子.

有沒有發(fā)現(xiàn)不同之處 ( ? ?ω?? )?

差分?jǐn)?shù)組有什么用?

先看一道題,

有n個(gè)數(shù)。

m次操作,每一次操作,給定l,r,del.將l~r區(qū)間的所有數(shù)增加del；

最后有q個(gè)詢問,給你 l,r ,每一次詢問求出l~r的區(qū)間和。

PS： 先進(jìn)行m個(gè)修改操作,后進(jìn)行查詢操作.

如果你是一個(gè)巨佬,你會(huì)"woc,線段樹裸題!" "woc,樹狀數(shù)組裸題!"

然而,今天我要BB的不是這些東西.

是差分?jǐn)?shù)組的運(yùn)用!

有沒有想法? 沒有的話那就我來有也是我來

考慮我們差分?jǐn)?shù)組記錄的是什么,它記錄的是當(dāng)前位置的數(shù)與上一個(gè)數(shù)的差值.

如果我們在差分?jǐn)?shù)組的 \(b_x\)減去\(del\) 在\(b_{y+1}\)位置處加上\(del\),就能達(dá)到整個(gè)區(qū)間修改的操作.

什么?不相信? 那我們來個(gè)栗子(要糖炒的

還是剛開始的栗子.

這樣是不是達(dá)到了區(qū)間修改操作,是不是! "是!,tql!!"

這樣我們就能做到\(O(1)\)修改啦!

我們?cè)?strong>定義兩個(gè)數(shù)組(先不要忘記我們的差分?jǐn)?shù)組為\(b_i\)

\(s_i\)代表\(\sum_{j=1}^{i} b_j\) (其實(shí)就是代表\(a[i]\) qwq

\(sum_i\)代表\(\sum_{j=1}^{i} s_j\) 即代表前綴和. qwq

容易發(fā)現(xiàn)的是 \(sum_r -sum_{l-1}=\sum_{i=l}^{r} s_i\)

什么不理解為什么是\(l-1\)？

那我們把式子展開看 qwq

\(sum_r=s_1+s_2+\dots+s_{l-1}+s_{l}+s_{l+1}+\dots+s_r\)

\(sum_{l-1}=s_1+s_2+\dots+s_{l-2}+s_{l-1}\)

兩個(gè)式子相減的話,我們得到的就是 \(s_l+\dots+s_r\) 即\(\sum_{i=l}^r s_i\)啦!

而我們?nèi)绻麥p去\(sum_l\)的話,就會(huì)多減去一個(gè)s_l,得到的值就不是\(\sum_{i=l}^r s_i\) 了!

emmmm 差點(diǎn)跑去講前綴和

所以說我們可以在修改操作完成之后,\(O(n)\)的計(jì)算我們的\(sum\)數(shù)組,然后在詢問的時(shí)候\(O(1)\)的輸出了.

具體這個(gè)題的代碼是這樣的↓

#include<bits/stdc++.h> using namespace std; int n,m,q,last,sum[10086],b[10086],s[10086]; int main() {cin>>n;//n個(gè)數(shù) for(int i=1,x;i<=n;i++){cin>>x;//這里實(shí)際上不需要a數(shù)組,視題而異 b[i]=x-last;//得到差分?jǐn)?shù)組 last=x;//別忘了變化last變量 }cin>>m;//m次操作for(int i=1,l,r,del;i<=m;i++){cin>>l>>r>>del;//在[l,r] 加上delb[l]+=del,b[r+1]-=del; }for(int i=1;i<=n;i++){s[i]=s[i-1]+b[i];//這里是處理我們的s數(shù)組 sum[i]=sum[i-1]+s[i];//處理我們的sum數(shù)組. }cin>>q;//q個(gè)詢問 for(int i=1,l,r;i<=q;i++){cin>>l>>r; //詢問[l,r]的區(qū)間和.cout<<sum[r]-sum[l-1]<<endl; //輸出即可. } }

剛剛涉及到的用途有

快速處理區(qū)間加減操作：\(O(1)\)

詢問區(qū)間和:\(O(n)\)處理\(O(1)\)查詢.

你以為差分只有這么多用處嗎?

利用差分?jǐn)?shù)組還能算出前綴和,看式子變形!

所以說,上面的代碼完全可以改一下,相信大家寫出來應(yīng)該會(huì)很容易. (其實(shí)是我懶 qwq

差分還有其他用途這里并沒有涉及到,所以還需要大家自己去發(fā)現(xiàn)去學(xué)習(xí) ┓( ′?｀ )┏

稱不上是拓展的拓展

xor差分

其實(shí)剛開始聽到這個(gè)名字還是很迷的emmm

感謝咕咕日?qǐng)?bào)的管理大大告訴我有這個(gè)東西才能學(xué)來分享給大家

這里給出如何求這種情況下的差分?jǐn)?shù)組.

n++;//原長(zhǎng)度要+1,因?yàn)槲覀儾罘謹(jǐn)?shù)組用到了右端點(diǎn)右邊一位. for(int i=1;i<=n;i++)b[i]=a[i]^a[i-1];//與上一位異或。

思想

類比于普通差分的思想,我們在被修改區(qū)間的左端點(diǎn)\(b_l\)^= 1,右端點(diǎn)的右側(cè)\(b_{r+1}\)^=1.

但是這樣可行嗎?

再來一個(gè)栗子 (干炒

我們將差分?jǐn)?shù)組一路滾過去 發(fā)現(xiàn)\(\sum_{j=1}^{i}b_j\)依舊等于\(a_i\)

這證明xor是可以差分的!

然后我們嘗試翻轉(zhuǎn)a_2 到a_4這段區(qū)間.

根據(jù)差分?jǐn)?shù)組的思想,我們將 \(b_2\)^=1 再將 \(b_5\)^=1

得到新的一組對(duì)應(yīng)關(guān)系是這樣的 ↓ qwq

我們?cè)侔巡罘謹(jǐn)?shù)組滾過去,發(fā)現(xiàn)依舊對(duì)應(yīng) ! 太神奇了!

事實(shí)證明這個(gè)是對(duì)的.(具體證明的話,我不會(huì) qwq.

例題

來一個(gè) 差分+二分 結(jié)合運(yùn)用的題目 -->p1083 借教室

看完題目了沒? 有沒有思路?

想一下,

在 一個(gè)訂單的起始天+要借的教室數(shù)量, 并在該訂單結(jié)束的那一天的下一天減去要借的教室數(shù)量

這樣我們?cè)倬S護(hù)一下前綴和,這就樣就能知道這些天中,我們借了多少教室! 是不是很巧妙qwq

然后我們?cè)俣钟唵螖?shù)量,嘗試滿足mid個(gè)訂單,(這個(gè)不會(huì)證明 QAQ)

因此我們ok函數(shù)這樣寫 ↓

IL bool ok(int now)//嘗試滿足now個(gè)訂單 {clear(delt);for(RI i=1;i<=now;i++){delt[s[i]]+=d[i];//s[i]為第i個(gè)訂單起始天delt[t[i]+1]-=d[i];//t[i]為第i個(gè)訂單結(jié)束天.}for(RI i=1;i<=n;i++){sum[i]=sum[i-1]+delt[i];//前綴和.if(sum[i]>could[i])return false;}return true; }

相信你隨隨便便也能切掉這個(gè)題了.

小結(jié)

差分?jǐn)?shù)組的話,一般并沒有裸的考查,但是差分?jǐn)?shù)組的思想啊,輔助啊,還是比較常用的qwq.

例如樹狀數(shù)組維護(hù)差分(到底是誰維護(hù)誰我也不是很清楚)qwq

(因?yàn)闃錉顢?shù)組是維護(hù)的前綴和啊,所以可以一起用)

推薦一篇很好的文章(講解樹狀數(shù)組與差分的結(jié)合使用)--->這里

Chanis寫的也很好啊qwq

如果非要說差分?jǐn)?shù)組的適用范圍的話,

它適用于離線的區(qū)間修改問題,在線的話就去碼 線段Tree 或 Tree狀數(shù)組就好了 qwq

課下作業(yè)

差分的板子題loj　洛谷

題解戳這里

p3943 星空 xor差分+最短路? (我也沒有做啊 qwq

p3948 數(shù)據(jù)結(jié)構(gòu) 一道差分的簡(jiǎn)單題 qwq.

這兩個(gè)題我只碼了第二題的代碼

第一題有時(shí)間再做 qwq

樹上差分

其實(shí)主要是為了講這個(gè)的qwq

2015,2016兩年Noip對(duì)于樹上差分都有考察 noip2015 運(yùn)輸計(jì)劃 noip2016 天天愛跑步

這兩個(gè)題涉及的知識(shí)點(diǎn)有著 樹上差分+二分+LCA\(\dots\),這是一些進(jìn)階的考查 其實(shí)是我不太會(huì)qwq

所以在這里打算單純地介紹一下樹上差分并講解一些例題.qwq

前置知識(shí)

需要知道的樹的性質(zhì):

樹上任意兩個(gè)點(diǎn)的路徑唯一.

任何子節(jié)點(diǎn)的父親節(jié)點(diǎn)唯一.(可以認(rèn)為根節(jié)點(diǎn)是沒有父親的)

如果你認(rèn)為你知道了這些你就能秒切這些樹上差分的題,那你就太低估這個(gè)東西了!

樹上差分的兩種基本操作用到了LCA,不了解LCA的話可以去這里面學(xué)一下

思想

類比于差分?jǐn)?shù)組,樹上差分利用的思想也是前綴和思想.(在這里應(yīng)該是子樹和思想.

當(dāng)我們記錄樹上節(jié)點(diǎn)被經(jīng)過的次數(shù),記錄某條邊被經(jīng)過的次數(shù)的時(shí)候.

如果每次強(qiáng)制dfs去標(biāo)記的話,時(shí)間復(fù)雜度將高到爆炸!

因此我們引入了樹上差分!

與樹上差分在一起的使用的是\(DFS\)，因?yàn)樵诨厮莸臅r(shí)候,我們可以計(jì)算出子樹的大小.

(這個(gè)應(yīng)該不用過多解釋

定義數(shù)組

\(cnt_i\)為節(jié)點(diǎn)i被經(jīng)過的次數(shù).

基本操作

1.點(diǎn)的差分

這個(gè)比較簡(jiǎn)單,所以先講這個(gè)qwq

例如,我們從 \(s-->t\) ,求這條路徑上的點(diǎn)被經(jīng)過的次數(shù).

很明顯的,我們需要找到他們的LCA,(因?yàn)檫@個(gè)點(diǎn)是中轉(zhuǎn)點(diǎn)啊qwq.

我們需要讓\(cnt_s++\),讓\(cnt_t++\)，而讓他們的\(cnt_{lca}--\)，\(cnt_{faher(lca)}--\);

可能讀著會(huì)有些難理解,所以我準(zhǔn)備了一個(gè)圖qwq

綠色的數(shù)字代表經(jīng)過次數(shù).

直接去標(biāo)記的話,可能會(huì)T到不行,但是我們現(xiàn)在在講啥?樹上差分啊!

根據(jù)剛剛所講,我們的標(biāo)記應(yīng)該是這樣的↓

考慮：我們搜索到s,向上回溯.

下面以\(u\)表示當(dāng)前節(jié)點(diǎn),\(son_i\)代表i的兒子節(jié)點(diǎn).(如果一些\(son\)不給出下標(biāo),即代表當(dāng)前節(jié)點(diǎn)\(u\)的兒子

每個(gè)\(u\)統(tǒng)計(jì)它的子樹大小,順著路徑標(biāo)起來.(即\(cnt_u+=cnt_{son}\))

我們會(huì)發(fā)現(xiàn)第一次從s回溯到它們的LCA時(shí)候,\(cnt_{LCA}+=cnt[son_{LCA}]\)

\(cnt_{LCA}=0\)! "不是LCA會(huì)被經(jīng)過一次嘛,為什么是0!"

別急,我們繼續(xù)搜另一邊.

繼續(xù)：我們搜索到t,向上回溯.

依舊統(tǒng)計(jì)每個(gè)u的子樹大小\(cnt_u+=cnt_{son}\)

再度回到\(LCA\) 依舊 是\(cnt_{LCA}+=cnt[son_{LCA}]\)

這個(gè)時(shí)候 \(cnt_{LCA}=1\) 這就達(dá)到了我們要的效果 (是不是特別優(yōu)秀 ( ? ?ω?? )?

擔(dān)憂： 萬一我們?cè)購(gòu)?span id="ze8trgl8bvbq" class="math inline">\(LCA\)向上回溯的時(shí)候使得其父親節(jié)點(diǎn)的子樹和為1怎么辦?

這樣我們不就使得其父親節(jié)點(diǎn)被經(jīng)過了一次? 因此我們需要在\(cnt_{faher(lca)}--\)

這樣就達(dá)到了標(biāo)記我們路徑上的點(diǎn)的要求! 厲不厲害 (oﾟ▽ﾟ)o tql!!

這樣點(diǎn)的差分應(yīng)該沒什么問題了吧 ,有問題可以問我的哦 qwq (如果我會(huì)的話.)

2.邊的差分

既然我們已經(jīng)get到了點(diǎn)的差分,那么我們邊的差分也是很簡(jiǎn)單啦!

機(jī)房某dalao:"這不和點(diǎn)差分標(biāo)記方式一樣嗎?不就是把邊塞給點(diǎn)嗎? 看我切了它!"

為這位大佬默哀一下 qwq.

的確,我們對(duì)邊進(jìn)行差分需要把邊塞給點(diǎn),但是,這里的標(biāo)記并不是同點(diǎn)差分一樣.

PS: 把邊塞給點(diǎn)的話,是塞給這條邊所連的深度較深的節(jié)點(diǎn). (即塞給兒子節(jié)點(diǎn)

先請(qǐng)大家思考\(5s\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

好,時(shí)間到,有沒有想到如何標(biāo)記?(只要畫圖模擬一下就可以啦! 上圖!

紅色邊為需要經(jīng)過的邊,綠色的數(shù)字代表經(jīng)過次數(shù)

正常的話,我們的圖是這樣的.↓

但是由于我們把邊塞給了點(diǎn),因此我們的圖應(yīng)該是這樣的↓

但是根據(jù)我們點(diǎn)差分的標(biāo)記方式來看的話顯然是行不通的,

這樣的話我們會(huì)經(jīng)過\(father_{LCA}--> LCA\)這一路徑.

因此考慮如何標(biāo)記我們的點(diǎn),來達(dá)到經(jīng)過紅色邊的情況

聰明的你一定想到了,這樣來標(biāo)記

\(cnt_s++\) ， \(cnt_t ++\) ，\(cnt_{LCA}-=2\)

這樣回溯的話,我們即可只經(jīng)過圖中紅色邊啦!(這里就不詳細(xì)解釋啦,原理其實(shí)相同 qwq

把邊塞入點(diǎn)中的代碼這樣寫.qwq(順便在搜索的時(shí)候處理即可

void dfs(int u,int fa,int dis) {//u為當(dāng)前節(jié)點(diǎn),fa為當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn),dis為從fa通向u的邊的邊權(quán).depth[u]=depth[fa]+1;f[u][0]=fa;//相信寫過倍增LCA的人都能看懂.init[u]=dis;//這里是將邊權(quán)賦給點(diǎn).for(int i=1;(1<<i)<=depth[u];i++)f[u][i]=f[f[u][i-1]][i-1];//預(yù)處理倍增數(shù)組.for(int i=head[u];i;i=edge[i].u){if(edge[i].v==fa)continue;dfs(edge[i].v,u,edge[i].w);}//這個(gè)每個(gè)人的寫法不一樣吧.//所以根據(jù)每個(gè)人的代碼風(fēng)格不一樣,碼出來的也不一樣 }

例題選講

代碼會(huì)在下面統(tǒng)一發(fā) qwq

先來一個(gè)簡(jiǎn)單題練練手 --->p3128 最大流
這個(gè)題應(yīng)該算是樹上差分的入門題
就是入門題qwq

題意簡(jiǎn)單概括一下
求被經(jīng)過次數(shù)最多的點(diǎn),(其實(shí)概括出來的話,這題就裸了.)

顯然,裸的點(diǎn)差分.

所以請(qǐng)?jiān)谡n下切掉它qwq.

再來一個(gè)簡(jiǎn)單題練手 --->p3258 松鼠的新家

也是一個(gè)簡(jiǎn)單的樹上差分的題.不過有一些小坑點(diǎn).

讀完題大家先思考\(5s\)

\(\vdots\)

時(shí)間到。

簡(jiǎn)單分析
很明顯,這是一道點(diǎn)差分.但是不同的是,我們需要在每個(gè)位置”中轉(zhuǎn)“一下.

即從 \(a_1-->a_2\) ，\(a_2-->a_3\) ，\(a_3-->a_4\) \(\dots\)我們會(huì)重復(fù)經(jīng)過\(a_2\)，\(a_3\)，\(\dots\)這一些點(diǎn).

因此我們經(jīng)過這些節(jié)點(diǎn)次數(shù)會(huì)被重復(fù)計(jì)算,因此,我們需要將其\(--\)

還要注意的是,當(dāng)我們到達(dá)\(a_n\)這一位置的時(shí)候,小熊會(huì)吃飯 qwq ,即在這里不會(huì)有糖果吃. 所以這個(gè)位置的經(jīng)過次數(shù)也需要\(--\).

代碼中需要注意的位置也只有這里 這樣↓

for(RI i=2;i<=n;i++)cnt[a[i]]--;

3.上點(diǎn)難度了 ----->p2680 運(yùn)輸計(jì)劃

(可能是因?yàn)槲姨趿?qwq

先感謝dalao的講解 @GMPotlc

讀完題,我們發(fā)現(xiàn),這是一道邊差分的題.

簡(jiǎn)單分析
于是建完邊我們先dfs一遍預(yù)處理出根節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的距離.并把邊權(quán)塞給點(diǎn)。

預(yù)處理距離的話只需要再在dfs中加入一句即可

Dis[edge[i].v]=Dis[u]+edge[i].w;

然后我們可以計(jì)算出每條航道間的距離,類似這樣

//\(query[i].dis\)代表第i個(gè)詢問兩航道之間的距離

//則\(query[i].dis=Dis[x]+Dis[y]-2*Dis[lca_{x,y}]\)

不能理解這個(gè)計(jì)算的話來看圖 qwq.

圖中給出的邊均為從根節(jié)點(diǎn)到達(dá)某節(jié)點(diǎn)的距離.

顏色對(duì)應(yīng)

我們發(fā)現(xiàn),實(shí)際只要記錄的距離僅為L(zhǎng)CA下面的紅色和綠色路徑.

而我們重復(fù)經(jīng)過了LCA上面的邊兩次."這沒用啊"

因此只要減去2*Dis_{LCA}即可.

考慮：

我們需要將被經(jīng)過次數(shù)最多,且邊權(quán)最大的邊刪去.

這樣能使我們所用總時(shí)間最大值盡可能小 (很明顯 qwq

要求最大值最小? 很明顯,我們想到了二分答案.

解決

既然想到了二分答案,那我們就二分這些路徑的長(zhǎng)度.(即工作時(shí)間.

如果一些路徑長(zhǎng)度大于當(dāng)前二分的mid,我們就需要記錄這些路徑上的邊其被經(jīng)過次數(shù).

(比mid小的路徑一定已經(jīng)合法,我們可以在mid時(shí)間內(nèi)完成任務(wù).)

假設(shè)路徑長(zhǎng)度大于mid的有num個(gè)

(我們找到被這些路徑共同經(jīng)過的最大的邊權(quán),刪去它,使得這些路徑長(zhǎng)度都小于mid,那么這個(gè)mid就是合法的.

小細(xì)節(jié):我們可以通過排序得到最大的路徑長(zhǎng)度,如果這條最長(zhǎng)的路徑減去被經(jīng)過次數(shù)<=mid,那這個(gè)mid就是合法的,我們就可以去尋找更優(yōu)解.

這里引用題解里的一句話

因?yàn)橐笄笞钚r(shí)間, 然而可以根據(jù)單調(diào)性可以通過二分一個(gè)時(shí)間來判定這個(gè)時(shí)間能不能成立.
也就是通過二分答案將一個(gè)求答案的問題轉(zhuǎn)化為\(log_{2}t_{\max}\)個(gè)判定性問題.

因此這個(gè)題就很簡(jiǎn)單了

PS:記得每次將標(biāo)記數(shù)組清零.(因?yàn)榇笥趍id的路徑長(zhǎng)度會(huì)變化.

(可能做法常數(shù)有些大,但是是可以過的.

(也可能是評(píng)測(cè)機(jī)看臉.第一次交T了一個(gè)點(diǎn),第二次交就A掉了 qwq.

上面三個(gè)題的代碼都在這里

小結(jié)

樹上差分的裸題還是比較少的(其實(shí)是我遇到的比較少吧 qwq.

因此樹上差分與其他算法的結(jié)合考察還是比較多的

例如剛剛講的運(yùn)輸計(jì)劃就是一個(gè) LCA+樹上差分+二分.

(其實(shí)樹上差分問題一定有LCA的 qwq)

BB in last

總的來說,差分?jǐn)?shù)組重點(diǎn)在于思想的運(yùn)用.

而樹上差分一般不會(huì)直接考裸題.

所以,我們需要掌握更多的算法. qwq

不會(huì)的可以問我 ,直到今年Noip我一直會(huì)在.

如果拿到省一的話,我會(huì)待的更久,拿不到就滾回去學(xué)文化課了 qwq

轉(zhuǎn)載于:https://www.cnblogs.com/-guz/p/9869748.html

總結(jié)

以上是生活随笔為你收集整理的差分数组 and 树上差分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。