3郭華陽RMQ與LC問題

RMQ LCA問題 湖南省長郡中學(xué)郭華陽 全文總攬 問題的提出問題的解決問題的應(yīng)用 I 問題的提出 問題的提出 LCA 基于有根樹最近公共祖先問題LCA T u v 在有根樹T中 詢問一個距離根最遠(yuǎn)的結(jié)點(diǎn)x 使得x同時為結(jié)點(diǎn)u v的祖先 問題的提出 RMQ 區(qū)間最小值詢問問題RMQ A i j 對于線性序列A中 詢問區(qū)間 i j 上的最小值特別的 若線性序列A任意兩相鄰元素相差為 1 那么建立在A上的RMQ稱為 1RMQ RMQ LCA在信息學(xué)競賽中 各種競賽試題中 如上海2003年省選的登山 2002年P(guān)OI的商務(wù)旅行等 都是這類問題的應(yīng)用及擴(kuò)展熟練的掌握及解決RMQ LCA問題 對于研究和競賽都是十分重要的 II 問題的解決 RMQ LCA問題的解決 在研究人員的努力下 RMQ LCA問題已經(jīng)獲得了比較完善的解決方案 這里我們只列出一些常用算法的適用范圍以及他們的時空復(fù)雜度 注 N表示問題規(guī)模 Q表示詢問次數(shù) RMQ LCA問題的解決 我們以O(shè) f N O g N 描述一個在線算法 在O f N 的時間內(nèi)完成預(yù)處理 在O g N 的時間內(nèi)完成一次詢問以O(shè) f N g N Q 描述一個離線算法的時間消耗 注 N表示問題規(guī)模 Q表示詢問次數(shù) RMQ LCA問題的解決 這些算法各自具有特點(diǎn) 但是針對問題過于狹窄 下文中我們將會看到 RMQ與LCA問題是可以互相轉(zhuǎn)化的 這就大大擴(kuò)寬了以下算法的應(yīng)用面 注 N表示問題規(guī)模 Q表示詢問次數(shù) RMQ向LCA的轉(zhuǎn)化 考察一個長度為N的序列A 按照如下方法將其遞歸建立為一棵樹 設(shè)序列中最小值為Ak 建立優(yōu)先級為Ak的根節(jié)點(diǎn)Tk 將A 1 k 1 遞歸建樹作為Tk的左子樹 將A k 1 N 遞歸建樹作為Tk的右子樹 不難發(fā)現(xiàn) 這棵樹是一棵優(yōu)先級樹 A 758110 我們以A序列為例建立樹T A 758110 1 將最小元素1作為根節(jié)點(diǎn)左右分別建樹 A 758110 1 1 0 右子樹只有一個結(jié)點(diǎn) 即10 A 758110 1 1 0 左子樹有三個結(jié)點(diǎn)7 5 8 A 758110 1 1 0 5 左子樹有三個結(jié)點(diǎn)7 5 8將最小元素5作為根節(jié)點(diǎn)左右分別建樹 A 758110 1 1 0 5 7 8 元素5的左右子樹都只有一個結(jié)點(diǎn) 分別是7 8 A 758110 1 1 0 5 7 8 這樣我們便得到了樹T RMQ向LCA的轉(zhuǎn)化 對于RMQ A i j 設(shè)序列中最小值為Ak 若k i j 那么答案為k 若k j 那么答案為RMQ A1 k 1 i j 若k i 那么答案為RMQ AK 1 N i j 不難發(fā)現(xiàn)RMQ A i j LCA T i j 這就證明了RMQ問題可以轉(zhuǎn)化為LCA問題 LCA向RMQ的轉(zhuǎn)化 對有根樹T進(jìn)行DFS 將遍歷到的結(jié)點(diǎn)按照順序記下 我們將得到一個長度為2N 1的序列 稱之為T的歐拉序列F每個結(jié)點(diǎn)都在歐拉序列中出現(xiàn) 我們記錄結(jié)點(diǎn)u在歐拉序列中第一次出現(xiàn)的位置為pos u 1 2 3 4 5 6 深度0 深度1 深度2 1 1 2 5 2 6 2 1 3 4 1 歐拉序列F 深度序列B 01212101010 Pos u 1281035 LCA向RMQ的轉(zhuǎn)化 根據(jù)DFS的性質(zhì) 對于兩結(jié)點(diǎn)u v 從pos u 遍歷到pos v 的過程中經(jīng)過LCA u v 有且僅有一次 且深度是深度序列B pos u pos v 中最小的即LCA T u v RMQ B pos u pos v 并且問題規(guī)模仍然是O N 的 LCA向RMQ的轉(zhuǎn)化 根據(jù)DFS的性質(zhì) 對于兩結(jié)點(diǎn)u v 從pos u 遍歷到pos v 的過程中經(jīng)過LCA u v 有且僅有一次 且深度是深度序列B pos u pos v 中最小的這就證明了LCA問題可以轉(zhuǎn)化成RMQ問題LCA與RMQ問題可以互相轉(zhuǎn)化 并且可以在O N 的時間內(nèi)完成 RMQ LCA算法關(guān)系圖 一般RMQ問題 1RMQ問題 LCA問題 ST算法 Tarjan算法 1RMQ算法 O N O N III 問題的應(yīng)用 問題的應(yīng)用 RMQ LCA問題在算法研究及信息學(xué)競賽中都發(fā)揮著十分重要的作用 它主要是以一種經(jīng)典算法及解題思想的形式出現(xiàn)本文主要以討論一道例題 水管局長 2006年冬令營試題 水管局長 原題 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)行一系列的準(zhǔn)備操作 如清洗 消毒等等 嘟嘟在控制中心一聲令下 這些水管的準(zhǔn)備操作同時開始 但由于各條管道的長度 內(nèi)徑不同 進(jìn)行準(zhǔn)備操作需要的時間可能不同 供水公司總是希望嘟嘟能找到這樣一條送水路徑 路徑上的所有管道全都準(zhǔn)備就緒所需要的時間盡量短 嘟嘟希望你能幫助他完成這樣的一個選擇路徑的系統(tǒng) 以滿足供水公司的要求 另外 由于MY市的水管年代久遠(yuǎn) 一些水管會不時出現(xiàn)故障導(dǎo)致不能使用 你的程序必須考慮到這一點(diǎn) 不妨將MY市的水管網(wǎng)絡(luò)看作一幅簡單無向圖 即沒有自環(huán)或重邊 水管是圖中的邊 水管的連接處為圖中的結(jié)點(diǎn) 題目模型簡述 定義 一條路徑的關(guān)鍵邊為其中費(fèi)用最大的邊 一條路徑的花費(fèi)為其關(guān)鍵邊的花費(fèi) 兩點(diǎn)之間的最短路為所有連接兩點(diǎn)的路徑中花費(fèi)最小的一條 給定帶權(quán)無向圖G及在G上的Q個操作形如 拆除無向邊 u v 詢問u v之間的最短路花費(fèi) 水管局長 你需要寫一個程序完成給出的操作數(shù)據(jù)范圍 結(jié)點(diǎn)數(shù)N 1000 邊數(shù)M 100000 操作數(shù)Q 100000 刪邊操作D 5000 水管局長 周戈林同學(xué)在2006年冬令營中已經(jīng)討論過相關(guān)的問題 并提出了解決的類普里姆算法類普里姆算法解決一次詢問需要O N2 的時間注意到詢問數(shù)可能達(dá)到105 類普里姆算法不能解決本題 為什么時間復(fù)雜度如此之高呢 水管局長 分析一下本題時間復(fù)雜度瓶頸所在 邊數(shù)過多 完成詢問的復(fù)雜度過高 我們將在后文逐個把這些問題解決 引入最小生成森林 引理一 任意詢問可以在G的最小生成森林中找到最優(yōu)解證明 記 P 表示路徑P中不在T中的邊數(shù)若 P 0 則P在T上 若 P 0 則存在一條邊 u v P T 引入最小生成森林 引理一 任意詢問可以在G的最小生成森林中找到最優(yōu)解證明 續(xù) 考察這條邊 u v 引入最小生成森林 引理一 任意詢問可以在G的最小生成森林中找到最優(yōu)解證明 續(xù) 考察這條邊 u v 根據(jù)最小生成森林的性質(zhì) 存在一條只有樹邊構(gòu)成的路徑P0連接u v兩點(diǎn) 并且P0的花費(fèi)不大于 u v 的花費(fèi) 引入最小生成森林 引理一 任意詢問可以在G的最小生成森林中找到最優(yōu)解證明 續(xù) 考察這條邊 u v 根據(jù)最小生成森林的性質(zhì) 存在一條只有樹邊構(gòu)成的路徑P0連接u v兩點(diǎn) 并且P0的花費(fèi)不大于 u v 的花費(fèi)將P中 u v 替換為路徑P0 P的總花費(fèi)不增且 P 減小 引入最小生成森林 引理一 任意詢問可以在G的最小生成森林中找到最優(yōu)解證明 續(xù) 由于 P 0 所以可以在有限次替換后將P變成一條T中的路徑這就證明了該引理 引入最小生成森林 引理一 任意詢問可以在G的最小生成森林中找到最優(yōu)解根據(jù)引理 我們只需要保存所有樹邊即可 這樣邊數(shù)下降到O N 級別 第一個問題被解決 完成詢問 我們來考慮第二個問題注意到最小生成森林中任意兩點(diǎn)之間的路徑是唯一的 我們可以采用DFS找出該路徑中的關(guān)鍵邊 時間消耗為O N 考慮到N 1000 Q 105 這樣的時間復(fù)雜度仍然不能很好解決本題 深入思考 詢問樹上兩點(diǎn)之間路徑上的最大邊 這種問題可以使用動態(tài)樹等工具實現(xiàn) 但是都過于復(fù)雜 為了找出一個簡單 實用的算法 我們需要仔細(xì)的研究最小生成森林的性質(zhì)Kruskal算法是建立最小生成森林中為我們所熟知的算法 以下我們將模擬一次Kruskal算法的執(zhí)行 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 我們使用Kruskal算法生成上圖的最小生成森林 將所有邊按照權(quán)值從小到大加入 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 加入邊 1 2 為樹邊注意到Query 1 2 的關(guān)鍵邊為 1 2 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 加入邊 1 3 為樹邊注意到Query 1 2 3 的關(guān)鍵邊為 1 3 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 加入邊 4 6 為樹邊注意到Query 4 6 的關(guān)鍵邊為 4 6 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 加入邊 5 6 為樹邊注意到Query 4 6 5 的關(guān)鍵邊為 5 6 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 加入邊 2 3 注意到已存在路徑 2 1 1 3 所以 2 3 非樹邊 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 加入邊 3 4 為樹邊注意到Query 1 2 3 4 5 6 的關(guān)鍵邊為 3 4 1 2 3 4 5 6 1 5 2 6 7 3 4 1 0 此時 我們已經(jīng)的到了最小生成森林T更重要的是 我們也已經(jīng)得到了所有詢問的回答 重要引理的發(fā)現(xiàn) 對Kruskal過程仔細(xì)思考 我們得出關(guān)鍵 引理二 任意兩點(diǎn)u v間最短路徑的關(guān)鍵邊 為執(zhí)行Kruskal算法中第一次將此兩點(diǎn)連通的樹邊 Kruskal生成順序森林 如何適當(dāng)?shù)膽?yīng)用引理二呢 所有的樹邊和結(jié)點(diǎn)需要被有機(jī)的結(jié)合起來 這里我們使用Kruskal生成順序森林 簡稱順序森林 仍然考慮下圖 Kruskal生成順序森林 順序森林的每個葉結(jié)點(diǎn)對應(yīng)原圖的一個結(jié)點(diǎn) 如下圖所示 葉結(jié)點(diǎn)Vi對應(yīng)原圖的結(jié)點(diǎn)i Kruskal生成順序森林 順序森林的每個葉結(jié)點(diǎn)對應(yīng)原圖的一個結(jié)點(diǎn) 如下圖所示 葉結(jié)點(diǎn)Vi對應(yīng)原圖的結(jié)點(diǎn)i V 1 V 2 V 3 V 4 V 5 V 6 Kruskal生成順序森林 樹邊Ei被加入時 該邊所連接的兩個連通塊在順序森林中必然是兩棵樹 V 1 V 2 V 3 V 4 V 5 V 6 Kruskal生成順序森林 建立順序森林結(jié)點(diǎn)與Ei相對應(yīng) 其左右孩子分別為兩個連通塊對應(yīng)樹的根結(jié)點(diǎn) V 1 V 2 V 3 V 4 V 5 V 6 Kruskal生成順序森林 我們模擬將所有的樹邊依次加入 V 1 V 2 V 3 V 4 V 5 V 6 Kruskal生成順序森林 添加樹邊 1 2 將原圖結(jié)點(diǎn)1 2合并為一個連通塊 我們建立順序森林結(jié)點(diǎn)E1 兩個兒子為V1 V2 V 1 V 2 V 3 V 4 V 5 V 6 E 1 Kruskal生成順序森林 添加樹邊 1 3 將原圖結(jié)點(diǎn)1 2 3合并為一個連通塊 我們建立順序森林結(jié)點(diǎn)E2 兩個兒子為E1 V3 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 Kruskal生成順序森林 類似的添加樹邊 4 6 時 建立順序森林結(jié)點(diǎn)E3 兩兒子為V4 V6 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 E 3 Kruskal生成順序森林 添加樹邊 5 6 時 建立順序森林結(jié)點(diǎn)E4 兩兒子為V5 E3 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 E 3 E 4 Kruskal生成順序森林 添加樹邊 3 4 時 建立順序森林結(jié)點(diǎn)E5 兩兒子為E2 E4 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 E 3 E 4 E 5 Kruskal生成順序森林 我們得到了圖G的最小生成順序森林 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 E 3 E 4 E 5 引入LCA解決問題 不難發(fā)現(xiàn) Query Vi Vj 即為順序森林中他們的最近公共祖先 根據(jù)已有的成果 我們可以在O N Q 的時間內(nèi)完成兩次刪邊操作之間的所有詢問可以采用Tarjan算法解決 水管局長 讓我們總結(jié)以上的算法流程 生成結(jié)束時的最小生成森林和順序森林 從后往前完成操作 對于刪邊操作 重新生成最小生成森林和順序森林 對于連續(xù)的詢問操作 將其作為離線LCA詢問在順序森林上處理 輸出答案 時間復(fù)雜度 在我的論文中以下結(jié)論被給出 生成 維護(hù)最小生成森林和順序樹總時間花費(fèi)為O Mlog2M DNa N 詢問可以在O Q ND 的時間內(nèi)解決總的時間復(fù)雜度為 O Mlog2M DNa N Q 小結(jié) 我們先發(fā)現(xiàn)了解題的關(guān)鍵所在 邊數(shù)過多 數(shù)據(jù)規(guī)模大 求解時間復(fù)雜度過高針對第一點(diǎn) 我們引入最小生成森林針對第二點(diǎn) 我們充分利用了經(jīng)典算法在已有的問題模型和算法上 合理的轉(zhuǎn)化 最終得到了本題的解決方案 總結(jié) RMQ LCA問題作為經(jīng)典問題無論在算法學(xué)習(xí)上還是實際應(yīng)用中都發(fā)揮了巨大的作用解決問題研究算法時 恰當(dāng)?shù)囊虢?jīng)典問題和經(jīng)典算法 無疑會大大加大我們的解題速度和精度 站在巨人的肩膀上 我們才能看得更高 更遠(yuǎn) 謝謝 敬請批評指正 引入最小生成森林的時間花費(fèi) 時間復(fù)雜度分為兩個部分 生成最小生成森林的時間消耗維護(hù)最小生成森林的時間消耗生成的復(fù)雜度由經(jīng)典的Kruskal算法給出 O Mlog2M 以下主要討論維護(hù)的時間消耗 引入最小生成森林的時間花費(fèi) 考察題目給出的刪邊操作若需刪除的邊非樹邊 那么不需要進(jìn)行維護(hù)否則 我們需要枚舉另一條邊來進(jìn)行補(bǔ)充 枚舉量高達(dá)O M 正難則反 若是向圖中添加一條新的邊呢 注意到一個重要的性質(zhì) 原非樹邊在添加新邊后仍然為非樹邊 算法只需在原樹邊與新邊中找出新的最小生成森林 引入最小生成森林的時間花費(fèi) 將刪邊操作轉(zhuǎn)化為添邊操作 從后往前執(zhí)行所有操作即可綜上 算法只需要在不超過N條邊中建立最小生成森林 復(fù)雜度為O Na N 注意到 最小順序森林的生成與最小生成森林是同步的 所以亦可以在O Na N 的時間內(nèi)完成 完成詢問的時間花費(fèi) 按照添邊操作 可以把操作序列分為很多段 對于連續(xù)兩個添邊操作之間的詢問操作 我們可以采取經(jīng)典算法解決 時間花費(fèi)為O N Q 總時間復(fù)雜度為 O ND Q 添邊操作詢問操作 詢問操作添邊操作詢問操作 詢問操作 SparseTable算法 一般RMQ的SparseTable ST 算法是基于倍增思想設(shè)計的O Nlog2N O 1 在線算法算法記錄從每個元素開始的連續(xù)的長度為2k的區(qū)間中元素的最小值 并以在常數(shù)時間內(nèi)解決詢問 SparseTable算法 對于RMQ A i j 我們可以找到兩段極大的長度為2的冪的區(qū)間 如圖 覆蓋 i j 由已經(jīng)計算的結(jié)果在O 1 的時間內(nèi)解決詢問 i j A SparseTable算法 利用倍增思想 在O Nlog2N 的時間內(nèi) 我們可以預(yù)處理所有長度為2的冪的區(qū)間的最小值 我們可以用O N 的時間處理長度為1的區(qū)間對于長度為2k的區(qū)間的最小值 可以由兩個長度為2k 1的區(qū)間的最小值得到 如圖 2k Tarjan算法 解決LCA問題的Tarjan算法利用并查集在一次DFS 深度優(yōu)先遍歷 中完成所有詢問 它是時間復(fù)雜度為O Na N Q 的離線算法 Tarjan算法 考察樹T中所有與結(jié)點(diǎn)u有關(guān)的詢問 u v p1 p2 對于子樹u中的結(jié)點(diǎn)v 滿足LCA u v v 對于子樹p1而非子樹u中的結(jié)點(diǎn)v 滿足LCA u v p1 對于子樹p2而非子樹p1中的結(jié)點(diǎn)v 滿足LCA u v p2 Tarjan算法 p1 p2 算法DFS有根樹T 定義從根節(jié)點(diǎn)到當(dāng)前正在遍歷的結(jié)點(diǎn)u的路徑為活躍路徑P 對于每個已經(jīng)遍歷過的結(jié)點(diǎn)x 我們使用并查集將其連接到P上距離其最近的結(jié)點(diǎn)F x 正在遍歷 F x F x F x Tarjan算法 p1 p2 正在遍歷 記錄與u有關(guān)的詢問集合為Q u 對于Q u 中的任意一組詢問LCA u v 如果v已經(jīng)遍歷過 那么答案即為F v 我們只需要維護(hù)當(dāng)前所有以遍歷結(jié)點(diǎn)的F即可 p1 p2 記錄與u有關(guān)的詢問集合為Q u 第一次遍歷結(jié)點(diǎn)u時 有F u u 2 遍歷完子樹u后 子樹u內(nèi)任意結(jié)點(diǎn)w均有F w u 回溯回結(jié)點(diǎn)p1時 子樹u內(nèi)任意結(jié)點(diǎn)w均有F w p1 使用