差分标记算法笔记
差分有：一維差分、多維差分、樹上差分 差分標(biāo)記一般求離線區(qū)間問題！（修改完后不再修改，然后修改結(jié)束后查詢）
對(duì)于帶有“將一段區(qū)間內(nèi)的每個(gè)數(shù)全部加上某個(gè)值”這種操作的題目，通常考慮差分原數(shù)列以簡(jiǎn)化情況，將對(duì)一段區(qū)間的操作轉(zhuǎn)化為對(duì)某兩個(gè)特定數(shù)的操作。
我們可以用樹狀數(shù)組來維護(hù)一個(gè)差分序列。差分序列的本質(zhì)是通過前綴和使區(qū)間修改轉(zhuǎn)換為單點(diǎn)修改。所以在查詢的時(shí)候只要輸出前綴和就可以了。
首先,給出一個(gè)問題:
給出n個(gè)數(shù)，再給出Q個(gè)詢問，每個(gè)詢問給出le，ri，x，要求你在le到ri上每一個(gè)值都加上x，而只給你O(n)的時(shí)間范圍，怎么辦？
思考一下:
如果暴力，卡一下le和ri，隨隨便便讓你O(n^2)T成狗。
用線段樹或樹狀數(shù)組搞一搞,抱歉,這個(gè)復(fù)雜度是O(Q logn)的,還是會(huì)T！(雖然他們解決別的題目很NB)
差分,沒錯(cuò),就是標(biāo)題，很高興O(n)+常數(shù)......
1.先另外開一個(gè)專門差分的數(shù)組(大小=題中的序列長(zhǎng)度)
2.假如在3~8的區(qū)間上加上5,那我們?cè)诓罘謹(jǐn)?shù)組中的3位置上加上一個(gè)5(原因暫時(shí)不懂沒關(guān)系,用筆先跟著模擬),再在8+1的位置上減一個(gè)5,如此操作完Q次。
3.假如我們只有這一次操作,開始統(tǒng)計(jì)答案,運(yùn)用前置和的思想,cfi=cf[i-1]+cf[i].那么你會(huì)發(fā)現(xiàn)(如果你模擬了的話),在3~8的區(qū)間上,你已經(jīng)使差分?jǐn)?shù)組全部加上了5(推廣到所有Q一起統(tǒng)計(jì)答案依舊正確)
4.再用O(n)的for把他們加到原序列之中去,輸出!
看一下復(fù)雜度,果然:O(常數(shù)*n).
博客上看拉個(gè)題目意思大概是：
給定一個(gè)長(zhǎng)度為N的序列： 首先進(jìn)行X次操作，每次操作在Li和Ri這個(gè)區(qū)間加上一個(gè)數(shù)Ci。
然后進(jìn)行Y次詢問，每次詢問Li到Ri的區(qū)間和。
初始序列都為0。
1<=N<=1000000,1<=X<=N, X<=Y<=N
1<=Li<=N,Li<=Ri<=N,|Ci|<=100000000000000
很多人第一眼看到這個(gè)題目第一反應(yīng)都是線段樹的裸題？但是本人認(rèn)為線段樹對(duì)于蒟蒻來說在大考中代碼實(shí)現(xiàn)復(fù)雜，如果寫的不太熟悉的話，運(yùn)用大量時(shí)間去實(shí)現(xiàn)其是不夠理智的，不過對(duì)于這個(gè)題利用差分?jǐn)?shù)組解題是個(gè)不錯(cuò)的選擇。
差分?jǐn)?shù)組(差分?jǐn)?shù)列)：
對(duì)于一個(gè)數(shù)組A[ ]，其差分?jǐn)?shù)組D[i]=A[i]-A[i-1] (i>0)且D[0]=A[0]
令SumD[i]=D[0]+D[1]+D[2]+…+D[i] （SumD[ ]是差分?jǐn)?shù)組D[ ]的前綴和）
則SumD[i]=A[0]+A[1]-A[0]+A[2]-A[1]+A[3]-A[2]+…+A[i]-A[i-1]=A[i]
即A[i]的差分?jǐn)?shù)組是D[i]， 而D[i]的前綴和是A[i]
對(duì)于“數(shù)列游戲”這題: 如果每次修改都修改從L到R的值的話，一定會(huì)TLE。
注意特殊處：這道題是先進(jìn)行整體區(qū)間修改，最后才統(tǒng)一查詢。 所以，我們只要維護(hù)一個(gè)差分?jǐn)?shù)組就行了。
維護(hù)差分?jǐn)?shù)組，對(duì)于將區(qū)間[L,R]加C，我們只需要將D[L]+C和D[R+1]-C 當(dāng)修改完畢后，我們先求一遍差分前綴和就得到了修改后的數(shù)組A[ ]，
然后再對(duì)A[ ]求一遍前綴和
這樣每次查詢的時(shí)候只要計(jì)算一次就可以得到結(jié)果了
總的來說差分?jǐn)?shù)組適用于離線的區(qū)間修改問題，如果是在線的話應(yīng)該用線段樹或其他數(shù)據(jù)結(jié)構(gòu)。
差分?jǐn)?shù)組其實(shí)就相當(dāng)于通過改變區(qū)間前端和末端與其他部分的差值，在最后進(jìn)行累加的時(shí)候?qū)嵭袑?duì)整個(gè)區(qū)間的值的改變。
但為什么要存差值呢？————因?yàn)閿?shù)列中的數(shù)滿A[i]=sum{D[1]…D[i]},便于用遞推求得最后的值。
---
差分?jǐn)?shù)組是什么呢？
http://www.cnblogs.com/widsom/p/7121047.html
差分?jǐn)?shù)組是前綴和的逆運(yùn)算，同樣運(yùn)用到容斥原理
一維：
l<=r
a[l]++;
a[r+1]--;
二維：
x1<=x2&&y1<=y2
a[x1][y1]++;
a[x1][y2+1]--;
a[x2+1][y1]--;
a[x2+1][y2+1]++;
三維：
x1<=x2&&y1<=y2&&z1<=z2
a[x1][y1][z1]++;
a[x2+1][y1][z1]--;
a[x1][y2+1][z1]--;
a[x1][y1][z2+1]--;
a[x1][y2+1][z2+1]++;
a[x2+1][y1][z2+1]++;
a[x2+1][y2+1][z1]++;
a[x2+1][y2+1][z2+1]--;
是不是很簡(jiǎn)單，是不是很有規(guī)律，相信你能寫出大于3維的情況了
算法筆記--差分標(biāo)記
所有元素初始值為0才能這么做。
①l--r全加1
a[l]++;
a[r+1]--;
求一遍前綴和為元素本身。
求兩遍前綴和為元素前綴和。
例題1：http://codeforces.com/problemset/problem/816/B
例題2：http://codeforces.com/problemset/problem/834/B
例題3：http://acm.hdu.edu.cn/showproblem.php?pid=1556
②l--r從1加到l-r+1
a[l]++;
a[r+1]-=l-r+2;
a[r+2]+=l-r+1;
求兩遍前綴和為元素本身。
求三遍前綴和為元素前綴和。
因?yàn)楦聲r(shí)復(fù)雜度是o(1)所以復(fù)雜度為求前綴和時(shí)的o(N)。
例題：http://arc077.contest.atcoder.jp/tasks/arc077_c
樹上差分（樹的前綴和）
近年的NOIp，似乎對(duì)于樹上差分的題目考察越來越熱（參見2015年提高組 運(yùn)輸計(jì)劃，2016年提高組 天天愛跑步）。這些題目都要知道在樹上從某個(gè)點(diǎn)到另一個(gè)點(diǎn)的所有路徑。但是，暴力求解這種題目經(jīng)常會(huì)TLE。這種題目需要使用樹上差分。在講樹上差分之前，首先需要知道樹的以下兩個(gè)性質(zhì)：
（1）任意兩個(gè)節(jié)點(diǎn)之間有且只有一條路徑。
（2）一個(gè)節(jié)點(diǎn)只有一個(gè)父親節(jié)點(diǎn)
這兩個(gè)性質(zhì)都很容易證明。那么我們知道，如果假設(shè)我們要考慮的是從u到v的路徑，u與v的lca是a，那么很明顯，如果路徑中有一點(diǎn)u'已經(jīng)被訪問了，且u'≠a，那么u'的父親也一定會(huì)被訪問，這是根據(jù)以上性質(zhì)可以推出的。所以，我們可以將路徑拆分成兩條鏈，u->a和a->v。那么樹上差分有兩種常見形式：（1）關(guān)于邊的差分；（2）關(guān)于節(jié)點(diǎn)的差分。
?、訇P(guān)于邊的差分：
將邊拆成兩條鏈之后，我們便可以像差分一樣來找到路徑了。因?yàn)殛P(guān)于邊的差分，a是不在其中的，所以考慮鏈u->a，則就要使cf[u]++，cf[a]--。然后鏈a->v，也是cf[v]++，cf[a]--。所以合起來便是cf[u]++，cf[v]++，cf[a]-=2。然后，從根節(jié)點(diǎn)，對(duì)于每一個(gè)節(jié)點(diǎn)x，都有如下的步驟：
（1）枚舉x的所有子節(jié)點(diǎn)u
（2）dfs所有子節(jié)點(diǎn)u
（3）cf[x]+=cf[u]
那么，為什么能夠保證這樣所有的邊都能夠遍歷到呢？因?yàn)槲覀儎倓傄呀?jīng)說了，如果路徑中有一點(diǎn)u'已經(jīng)被訪問了，且u'≠a，那么u'的父親也一定會(huì)被訪問。所以u(píng)'被訪問幾次，它的父親也就因?yàn)閡'被訪問了幾次。所以就能夠找出所有被訪問的邊與訪問的次數(shù)了。路徑求交等一系列問題就是通過這個(gè)來解決的。因?yàn)槊總€(gè)點(diǎn)都只會(huì)遍歷一次，所以其時(shí)間復(fù)雜度為O(n).
?、陉P(guān)于點(diǎn)的差分：
還是與和邊的差分一樣，對(duì)于所要求的路徑，拆分成兩條鏈。步驟也和上面一樣，但是也有一些不同，因?yàn)殛P(guān)于點(diǎn)，u與v的lca是需要包括進(jìn)去的，所以要把lca包括在某一條鏈中，最后對(duì)cf數(shù)組的操作便是cf[u]++，cf[v]++，cf[a]--，cf[father[a]]--。其時(shí)間復(fù)雜度也是一樣的O(n).
通過以上的描述，如果你還是不太能理解，那么以下兩個(gè)題目可能可以幫助你理解：
USACO 最大流（樹上差分）https://www.luogu.org/problem/show?pid=3128
NOIp2015 運(yùn)輸計(jì)劃（樹上差分+二分）https://www.luogu.org/problem/show?pid=2680
轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/9354335.html
總結(jié)
- 上一篇： git 与团队协同开发，避免冲掉别人代码
- 下一篇： 洛谷P4145 上帝造题的⑦minute