3郭華陽RMQ與LC問題

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