1、淺談分塊思想 在一類數(shù)據(jù)處理問(wèn)題中的應(yīng)用,北京市第八十中學(xué) 羅劍橋,本文討論的范圍,一類與線性序列和樹形結(jié)構(gòu)有關(guān)的數(shù)據(jù)處理問(wèn)題 特征： 1. 在競(jìng)賽中常常出現(xiàn) 2. 沒有專門的數(shù)據(jù)結(jié)構(gòu)解法 或者數(shù)據(jù)結(jié)構(gòu)解法十分復(fù)雜,什么是分塊思想,將一個(gè)問(wèn)題分解為若干個(gè)規(guī)模較小的子問(wèn)題 優(yōu)勢(shì)： 1. 如果子問(wèn)題的規(guī)模很小，可以設(shè)計(jì)關(guān)于子問(wèn)題規(guī)模的 復(fù)雜度較高的算法； 2. 如果子問(wèn)題的數(shù)目很少，可以對(duì)每類子問(wèn)題使用復(fù)雜 度與整個(gè)問(wèn)題規(guī)模有關(guān)的算法； 3. 如果每個(gè)子問(wèn)題內(nèi)部的元素具有共同的性質(zhì)，可以使 用針對(duì)性的算法。,線性序列的分塊化,從第一個(gè)元素開始，每連續(xù)的 S 個(gè)元素組成一個(gè)塊。若剩余的元素不足 S

2、個(gè)，令它們組成一個(gè)塊。 例子：序列元素?cái)?shù)目 N = 7，塊的大小S = 3.,線性序列的分塊化：性質(zhì),設(shè) N 為序列的元素?cái)?shù)目，S 為塊的大小。 1. 塊的數(shù)目不超過(guò) N / S + 1. 2. 對(duì)于任意區(qū)間 L, R, 可以分解成若干個(gè)完整的 塊以及剩余的不超過(guò) 2S 個(gè)元素。 如果能在塊的層次上概括塊內(nèi)元素的信息，并且 可以快速將不同部分的信息合并，就能夠快速地得到任意區(qū)間的信息了。,例一,一個(gè) N 個(gè)數(shù)的序列。你要執(zhí)行 M 次操作。 操作有兩種類型： 1. 從第一個(gè)數(shù)開始，每隔 Di 個(gè)位置的數(shù)加上 Xi。 2. 查詢區(qū)間 Li, Ri 的所有元素的和。 1 = N, M = 105.

3、任意時(shí)刻所有數(shù)均為絕對(duì)值不超過(guò)109的整數(shù)。,例一：樣例,N = 5, M = 4. 7 15 11 8 2ADD: Di = 2, Xi = 1 8 15 12 8 3 ASK: Li = 1, Ri = 4 answer: 8 + 15 + 12 + 8 = 43ADD: Di = 4, Xi = -5 3 15 12 8 3 ASK: Li = 1, Ri = 4 answer: 3 + 15 + 12 + 8 = 38,例一：分析,將序列分塊，令每塊的大小為 。 考慮在塊的層次上維護(hù)每個(gè)塊的所有元素的和。 首先，預(yù)處理的復(fù)雜度為 O(N) 。 1.對(duì)于詢問(wèn)操作，只需計(jì)算出詢問(wèn)區(qū)間對(duì)應(yīng)的

4、完整的塊與多余的元素的和，時(shí)間復(fù)雜度為 O( )。 N = 10. Ask: Li = 3, Ri = 8. 3, 4, 5 1, 2, 3 7, 8, 9 10 answer = 5 + 6 + 7 + 8 = 26. 2.對(duì)于修改操作，復(fù)雜度還是很高，怎么辦呢?,例一：分析,這時(shí)還是要用到分塊的思想。 發(fā)現(xiàn)，只有當(dāng) Di 比較小的時(shí)候修改的元素才會(huì)很多。 解決方法： 1. 每個(gè)元素和塊只考慮 Di = 的修改操作的影響。 2. 用數(shù)組記錄 Di 的每個(gè) Di 的修改量的和。 在查詢時(shí)枚舉每個(gè)小于 的 Di，O(1) 計(jì)算對(duì)答案的影響即可。 此算法總的時(shí)間復(fù)雜度為O(n + m )。,例一：

5、分析,N = 10 3, 4, 5 1, 2, 3 7, 8, 9 10 1.ADD Di = 1, Xi = 3 Sum: 12, 6, 24, 10; Di13: 3, 0, 0. 2.ADD Di = 4, Xi = 1. 4, 4, 5 1, 3, 3 7, 8, 10 10 Sum: 13, 7, 25, 10; Di13: 3, 0, 0.,樹形結(jié)構(gòu)的分塊化,樹的 DFS 序： 從根開始深度優(yōu)先遍歷，每次遇到一個(gè)點(diǎn)進(jìn)棧或出棧，就把它放到 DFS 序列的末尾。,1 1, 2 1, 2, 4 1, 2, 4, 4 1, 2, 4, 4, 5 1, 2, 4, 4, 5, 5 1, 2,

6、 4, 4, 5, 5, 2 1, 2, 4, 4, 5, 5, 2, 3 1, 2, 4, 4, 5, 5, 2, 3, 3 1, 2, 4, 4, 5, 5, 2, 3, 3, 1,DFS序的性質(zhì),1. 相鄰兩個(gè)元素之間僅有三種關(guān)系： 同一個(gè)點(diǎn)；父子關(guān)系；兄弟關(guān)系。 2. 任意兩項(xiàng)之間的連續(xù)子序列恰好對(duì)應(yīng)了樹上 一條路徑，路徑上除 LCA 以外的點(diǎn)至少出現(xiàn)1次。 3. DFS 序列中任意一個(gè)區(qū)間以及這個(gè)區(qū)間所有元素 的 LCA 恰好對(duì)應(yīng)樹上的一個(gè)連通塊。 將 DFS 序列分塊，每一塊與其 LCA 就對(duì)應(yīng)了樹上的一個(gè)連通塊！,例二,一個(gè) N 個(gè)點(diǎn)的樹。邊有權(quán)值。 你需要計(jì)算對(duì)于每個(gè)點(diǎn)，其他所

7、有點(diǎn)到它的距離中第 K 小的值。 1 = K N = 50,000. 邊的權(quán)值為絕對(duì)值不超過(guò)1,000的整數(shù)。,例二：樣例,1,2,3,4,5,10,3,7,5,N = 5, K = 2.,distance1: 3, 8, 10, 10 distance2: 3, 5, 7, 13 distance3: 10, 13, 18, 20 distance4: 5, 8, 12, 18 distance5: 7, 10, 12, 20,例二：分析,相鄰的點(diǎn)之間的答案具有很強(qiáng)的相關(guān)性： 設(shè)點(diǎn) u 的答案為 ansu. 若存在一條邊 (u, v) 的權(quán)值等于 c, 則點(diǎn) v 的答案是 ansu - c

8、到 ansu + c 之間的數(shù)。 考慮將樹分成若干個(gè)規(guī)模等于 S 的連通塊。 一次計(jì)算出一個(gè)連通塊內(nèi)所有點(diǎn)的答案。,例二：分析,對(duì)一個(gè)連通塊，以塊內(nèi)的某個(gè)點(diǎn)為根。 性質(zhì) 1： 無(wú)論以塊內(nèi)的哪個(gè)點(diǎn)為根，每個(gè)點(diǎn)到根的路徑上的第一個(gè)塊內(nèi)的點(diǎn)是不變的。 推論： 將所有點(diǎn)按最近塊內(nèi)祖先分類。 考慮同類的點(diǎn) u, v，設(shè) p 為 u 和 v 的最近塊內(nèi)祖先。 則 點(diǎn) u 到根的距離 點(diǎn) u 到 p 的距離 = 點(diǎn) v 到 p 的距離,例二：分析,例二：分析,1. 對(duì)于一個(gè)連通塊，首先以一個(gè)點(diǎn) r 遍歷全樹，計(jì)算出每類點(diǎn)到最近塊內(nèi)祖先 (LIA) 的距離。 并且將每類點(diǎn)按到 LIA 的距離排序。 2. 然后

9、，依次計(jì)算塊內(nèi)每個(gè)點(diǎn)的答案。 使用二分答案的辦法。 3. 如何統(tǒng)計(jì)到點(diǎn) ri 距離不超過(guò) x 的點(diǎn)的數(shù)目？ 以 ri 為根遍歷塊內(nèi)的所有點(diǎn)，算出它們到 ri 的距離。 對(duì)每類點(diǎn)二分查找 加上 LIA 到 ri 的距離以后不 超過(guò) x 的最大的數(shù)的位置即可。,例二：復(fù)雜度分析,連通塊的大小為 S。 第一次遍歷和排序的時(shí)間復(fù)雜度為 O(NlogN). 每個(gè)點(diǎn)，二分答案和查找的時(shí)間復(fù)雜度為 O(log2N). 所以處理一個(gè)塊的復(fù)雜度是 O(NlogN + Slog2N). 總的時(shí)間復(fù)雜度為 O(N2logN/S + NSlog2N). 如果設(shè) S = ， 總的時(shí)間復(fù)雜度為 O(N1.5log1.5N

10、) .,分塊與預(yù)處理,預(yù)處理的條件 線性序列上，預(yù)處理任意兩塊之間的信息，每次詢問(wèn)時(shí)經(jīng)過(guò)若干次增量得到詢問(wèn)區(qū)間的信息。 樹形結(jié)構(gòu)中，貪心算法標(biāo)記若干關(guān)鍵點(diǎn)，預(yù)處理任意兩個(gè)關(guān)鍵點(diǎn)之間的信息，每次詢問(wèn)時(shí)經(jīng)過(guò)若干次增量得到詢問(wèn)路徑的信息。,分塊與離線算法,與分塊與預(yù)處理的方法有一定的相似之處。 核心： 沒有必要記錄過(guò)多信息， 在預(yù)處理的同時(shí)計(jì)算詢問(wèn)的答案。 具體可參考論文。,感謝,感謝中國(guó)計(jì)算機(jī)學(xué)會(huì)。 感謝我的指導(dǎo)老師賈志勇老師長(zhǎng)期以來(lái)的關(guān)心和幫助。 感謝集訓(xùn)隊(duì)的胡偉棟教練和唐文斌教練。 特別感謝北京人大附中的范浩強(qiáng)同學(xué)的大力幫助和啟發(fā)。 感謝學(xué)長(zhǎng)黃紀(jì)元同學(xué)的幫助。 感謝我的父母對(duì)我的無(wú)微不至的關(guān)心和照顧。,Thank you.,Questions are welcome,參考文獻(xiàn),Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. “Introduction to Algorithms (2nd ed.)”, 潘金貴等譯，機(jī)械工業(yè)出版社. Jon Kleinberg, Eva Tardos. “Algorithm Design”