信息學(xué)數(shù)據(jù)結(jié)構(gòu)rmqlca問題

1、RMQ&LCA問題雅禮 朱全民思考問題讀入n個數(shù)：a1,a2,a3,an共有m個操作，每種操作分兩類：1、修改一個值2、詢問某個區(qū)間中的最小值n=100000m=100000 （m為操作次數(shù)）樸素的方法，時間復(fù)雜度為 O（nm）RMQ問題已知長度為L 的數(shù)列A ，詢問區(qū)間l, r 中的最值。若詢問的次數(shù)較少，可以用線性的復(fù)雜度來查詢，但如果詢問的次數(shù)過多且L 過大，那么復(fù)雜度就會很高。所以需要更快速的查找方法。 RMQ示例RMQ的主要算法在線算法：線段樹 O(nlogn) 離線算法：ST算法（動態(tài)規(guī)劃） O(nlogn)-O(1)離線算法：笛卡爾樹O(n)ST算法（Sparse Table）S

2、T算法運用的主要思想是倍增思想。設(shè)fi,j表示從i開始向后數(shù)2j個元素的最小值遞推方程就是 fi,j:=min(fi,j-1,fi+2j-1,j-1);邊界：fi,0:=ai;設(shè) k:=trunc(ln(j-i+1)/ln(2) RMQ(i,j):=min(fi,k,fj-2k+1,k);RMQ代碼 Read(n, q); for i := 1 to n do Read(di, 0); for j := 1 to Trunc(Ln(n) / Ln(2) do for i := 1 to n - 1 shl j + 1 do di,j := Min(di,j-1, di+1 shl (j-1),

3、j-1); for i := 1 to q do begin Read(a, b); k := Trunc(Ln(b - a + 1) / Ln(2); rmq := Min(da, k, db - 1 shl k + 1, k); Writeln(rmq); #define Min(a, b) (a)(b)?(a):(b) int Dmin5000520; / 最小值的DP 矩陣 int num50005; / 記錄區(qū)間中的數(shù)據(jù) void Init(int N) / 計算DP 矩陣 DP 規(guī)則如上 int i, j, M; for (i=1; i=N; i+) Dmini0=numi; fo

4、r (i=1, M=1; M0; j-) Dminji=Dminji-1; if (j+(1(i-1)=N) Dminji=Min(Dminji, Dminj+(1(i-1)i-1); return; int RMQ(int l, int r) / 計算l, r 區(qū)間中的最小值 int i, j, k; k=r-l+1; / 記錄區(qū)間中數(shù)字的個數(shù) for (i=0, j=1; 2*j=k; j=1, i+); int a=Min(Dminli, Dminr-j+1i); return a; 思考怎樣求一個數(shù)字矩陣中的RMQ?LCA 問題最近公共祖先( Lowest Common Ancesto

5、rs ) 對于有根樹T 的兩個結(jié)點u 、v ，LCA(T, u, v) 表示一個結(jié)點x ，滿足x 是u 、v 的祖先且x 的深度盡可能大（即離根最遠(yuǎn)）。Tarjan離線算法1 、在并查集中建立僅包含x 結(jié)點的集合，即Fax=x; 2 、處理x 的所有孩子，處理完每個孩子后，令Fa 孩子=x ，即將孩子和x 所在集合合并； 3 、全部孩子處理完后，將x 標(biāo)記為處理結(jié)束； 4 、處理所有與x 相關(guān)的詢問。對于每個詢問LCA(x, y) ，若y 已被標(biāo)記，則記錄下LCA(x, y)=Find(y) ，即y 所在集合的代表元素。LCA 與RMQ RMQ 向LCA 轉(zhuǎn)化：設(shè)序列A 的長度為N 1 、設(shè)序

6、列中最小值為為Ak ，建立優(yōu)先級為Ak 的根結(jié)點Tk ；2 、將A1.k-1 遞歸建樹作為Tk 的左子樹； 3 、將Ak+1.N 遞歸建樹作為Tk 的右子樹。 RMQ(A, i, j) 查詢Ai.j 的最值即為LCA(T, i, j) 。 LCA 向RMQ 轉(zhuǎn)化： 對有根樹T 進(jìn)行DFS ，將遍歷到的結(jié)點按照順序記下，得到一個長度為2*N-1 的序列，稱之為T 的歐拉序列F ，每個結(jié)點在歐拉序列中出現(xiàn)，記錄posu 為結(jié)點u 在歐拉序列中 第一次出現(xiàn)的位置。 LCA(T, u, v)=RMQ(B, pos(u), pos(v) 笛卡爾樹(Cartesian Tree)算法這個方法的精髓在于將R

7、MQ問題轉(zhuǎn)化為LCA問題。笛卡爾樹的定義:對于一個數(shù)組A來說，笛卡爾樹的根的編號是這個數(shù)組的最小值的所在的編號k。他的左子樹就是在數(shù)組A1.k-1上的一棵笛卡爾樹，右子樹是一棵在數(shù)組Ak+1.n的一棵笛卡爾樹。Cartesian 樹的建立首先，先從A1開始建立，以后每次加一個數(shù)，就修改Cartesian數(shù)，不難發(fā)現(xiàn)，這個數(shù)一定在這棵樹的最右邊的路徑上。而且一定沒有右孩子（應(yīng)為數(shù)組為樹的中序遍歷），所以，只沿著最右路徑自底向上把各個節(jié)點p和Ai做比較，如果pAi，那么比較p的父親與Ai，如果Aip的父親，那么Ai為p的父親的右孩子，而p則改為Ai的左孩子。因為每個節(jié)點最多進(jìn)入和退出最右路徑各一次

8、，所以，均攤時間復(fù)雜度為O(n)。定理：數(shù)組A的Cartesian數(shù)記為C(A)，則RMQ(A, i, j) = LCA(C(A), i, j).水管局長（原題）SC省MY市有著龐大的地下水管網(wǎng)絡(luò)，嘟嘟是MY市的水管局長（就是管水管的啦），嘟嘟作為水管局長的工作就是：每天供水公司可能要將一定量的水從x處送往y處，嘟嘟需要為供水公司找到一條從A至B的水管的路徑，接著通過信息化的控制中心通知路徑上的水管進(jìn)入準(zhǔn)備送水狀態(tài)，等到路徑上每一條水管都準(zhǔn)備好了，供水公司就可以開始送水了。嘟嘟一次只能處理一項送水任務(wù)，等到當(dāng)前的送水任務(wù)完成了，才能處理下一項。在 處理每項送水任務(wù)之前，路徑上的水管都要進(jìn)行一系

9、列的準(zhǔn)備操作，如清洗、消毒等等。嘟嘟在控制中心一聲令下，這些水管的準(zhǔn)備操作同時開始，但由于各條管道 的長度、內(nèi)徑不同，進(jìn)行準(zhǔn)備操作需要的時間可能不同。供水公司總是希望嘟嘟能找到這樣一條送水路徑，路徑上的所有管道全都準(zhǔn)備就緒所需要的時間盡量短。嘟 嘟希望你能幫助他完成這樣的一個選擇路徑的系統(tǒng)，以滿足供水公司的要求。另外，由于MY市的水管年代久遠(yuǎn)，一些水管會不時出現(xiàn)故障導(dǎo)致不能使用，你的程序必須考慮到這一點。不妨將MY市的水管網(wǎng)絡(luò)看作一幅簡單無向圖（即沒有自環(huán)或重邊）：水管是圖中的邊，水管的連接處為圖中的結(jié)點。題目模型簡述定義：一條路徑的關(guān)鍵邊為其中費用最大的邊；一條路徑的花費為其關(guān)鍵邊的花費；兩

10、點之間的最短路為所有連接兩點的路徑中花費最小的一條；給定帶權(quán)無向圖G及在G上的Q個操作形如：拆除無向邊(u, v)；詢問u、v之間的最短路花費；水管局長你需要寫一個程序完成給出的操作數(shù)據(jù)范圍：結(jié)點數(shù) N 1000；邊數(shù) M 100000；操作數(shù) Q 100000；刪邊操作 D 5000；水管局長分析一下本題時間復(fù)雜度瓶頸所在：邊數(shù)過多；完成詢問的復(fù)雜度過高；我們將在后文逐個把這些問題解決引入最小生成森林引理一：任意詢問可以在G的最小生成森林中找到最優(yōu)解證明：記(P)表示路徑P中不在T中的邊數(shù)若(P) = 0，則P在T上；若(P) 0，則存在一條邊(u, v)P T引入最小生成森林引理一：任意詢

11、問可以在G的最小生成森林中找到最優(yōu)解證明（續(xù)）：考察這條邊(u, v)：引入最小生成森林引理一：任意詢問可以在G的最小生成森林中找到最優(yōu)解證明（續(xù)）：考察這條邊(u, v)：根據(jù)最小生成森林的性質(zhì)，存在一條只有樹邊構(gòu)成的路徑P0連接u、v兩點，并且P0的花費不大于(u, v)的花費引入最小生成森林引理一：任意詢問可以在G的最小生成森林中找到最優(yōu)解證明（續(xù)）：考察這條邊(u, v)：根據(jù)最小生成森林的性質(zhì)，存在一條只有樹邊構(gòu)成的路徑P0連接u、v兩點，并且P0的花費不大于(u, v)的花費將P中(u, v)替換為路徑P0，P的總花費不增且(P) 減小引入最小生成森林引理一：任意詢問可以在G的最小

12、生成森林中找到最優(yōu)解證明（續(xù)）：由于(P) 0，所以可以在有限次替換后將P變成一條T中的路徑這就證明了該引理引入最小生成森林引理一：任意詢問可以在G的最小生成森林中找到最優(yōu)解根據(jù)引理，我們只需要保存所有樹邊即可，這樣邊數(shù)下降到O(N)級別，第一個問題被解決。完成詢問我們來考慮第二個問題注意到最小生成森林中任意兩點之間的路徑是唯一的。我們可以采用DFS找出該路徑中的關(guān)鍵邊，時間消耗為O(N)考慮到N = 1000、Q = 105，這樣的時間復(fù)雜度仍然不能很好解決本題深入思考詢問樹上兩點之間路徑上的最大邊，這種問題可以使用動態(tài)樹等工具實現(xiàn)，但是都過于復(fù)雜。為了找出一個簡單、實用的算法，我們需要仔細(xì)

13、的研究最小生成森林的性質(zhì)Kruskal算法是建立最小生成森林中為我們所熟知的算法，以下我們將模擬一次Kruskal算法的執(zhí)行123456152673410我們使用Kruskal算法生成上圖的最小生成森林，將所有邊按照權(quán)值從小到大加入123456152673410加入邊(1, 2)為樹邊注意到Query(1, 2)的關(guān)鍵邊為(1, 2)123456152673410加入邊(1, 3)為樹邊注意到Query(1|2, 3)的關(guān)鍵邊為(1, 3)123456152673410加入邊(4, 6)為樹邊注意到Query(4, 6)的關(guān)鍵邊為(4, 6)123456152673410加入邊(5, 6)為樹

14、邊注意到Query(4|6, 5)的關(guān)鍵邊為(5, 6)123456152673410加入邊(2, 3)注意到已存在路徑(2, 1) (1, 3)，所以(2, 3)非樹邊123456152673410加入邊(3, 4)為樹邊注意到Query(1|2|3,4|5|6)的關(guān)鍵邊為(3, 4)123456152673410此時，我們已經(jīng)的到了最小生成森林T更重要的是，我們也已經(jīng)得到了所有詢問的回答！重要引理的發(fā)現(xiàn)對Kruskal過程仔細(xì)思考，我們得出關(guān)鍵：引理二：任意兩點u、v間最短路徑的關(guān)鍵邊，為執(zhí)行Kruskal算法中第一次將此兩點連通的樹邊！Kruskal生成順序森林如何適當(dāng)?shù)膽?yīng)用引理二呢？所

15、有的樹邊和結(jié)點需要被有機(jī)的結(jié)合起來，這里我們使用Kruskal生成順序森林（簡稱順序森林）仍然考慮下圖：Kruskal生成順序森林順序森林的每個葉結(jié)點對應(yīng)原圖的一個結(jié)點，如下圖所示，葉結(jié)點Vi對應(yīng)原圖的結(jié)點iKruskal生成順序森林順序森林的每個葉結(jié)點對應(yīng)原圖的一個結(jié)點，如下圖所示，葉結(jié)點Vi對應(yīng)原圖的結(jié)點iV1V2V3V4V5V6Kruskal生成順序森林樹邊Ei被加入時，該邊所連接的兩個連通塊在順序森林中必然是兩棵樹V1V2V3V4V5V6Kruskal生成順序森林建立順序森林結(jié)點與Ei相對應(yīng)，其左右孩子分別為兩個連通塊對應(yīng)樹的根結(jié)點V1V2V3V4V5V6Kruskal生成順序森林我們

16、模擬將所有的樹邊依次加入：V1V2V3V4V5V6Kruskal生成順序森林添加樹邊(1, 2)，將原圖結(jié)點1、2合并為一個連通塊；我們建立順序森林結(jié)點E1，兩個兒子為V1、V2V1V2V3V4V5V6E1Kruskal生成順序森林添加樹邊(1, 3)，將原圖結(jié)點1、2、3合并為一個連通塊；我們建立順序森林結(jié)點E2，兩個兒子為E1、V3V1V2V3V4V5V6E1E2Kruskal生成順序森林類似的添加樹邊(4, 6)時，建立順序森林結(jié)點E3，兩兒子為V4、V6V1V2V3V4V5V6E1E2E3Kruskal生成順序森林添加樹邊(5, 6)時，建立順序森林結(jié)點E4，兩兒子為V5、E3V1V2V3V4V5V6E1E2E3E4Kruskal生成順序森林添加樹邊(3, 4)時，建立順序森林結(jié)點E5，兩兒子為E2、E4V1V2V3V4V5V6E1E2E3E4E5Kruskal生成順序森林我們得到了圖G的最小生成順序森林V1V2V3V4V5V6E1E2E3E4E5引入LCA解決問題！不難發(fā)現(xiàn)，Query(Vi, Vj)即為順序森林中他們的最近公共祖先！根據(jù)已有的成