算法合集之RMQ與LCA問題PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 算法合集之算法合集之RMQ與與LCA問題問題 第1頁/共85頁 第2頁/共85頁 第3頁/共85頁 第4頁/共85頁 第5頁/共85頁 第6頁/共85頁 算法名稱針對(duì)問題時(shí)間消耗空間消耗 ST算法一般RMQ問題O(Nlog2N) Tarjan算法LCA問題O(N) 1RMQ算法 1RMQ問題O(N) 注：N表示問題規(guī)模，Q表示詢問次數(shù) 第7頁/共85頁 算法名稱針對(duì)問題時(shí)間消耗空間消耗 ST算法一般RMQ問題O(Nlog2N)-O(1)O(Nlog2N) Tarjan算法LCA問題O(Na(N) + Q)O(N) 1RMQ算法 1RMQ問題O(N)-O(1)O(N) 注：N表示問題規(guī)

2、模，Q表示詢問次數(shù) 第8頁/共85頁 算法名稱針對(duì)問題時(shí)間消耗空間消耗 ST算法一般RMQ問題O(Nlog2N)-O(1)O(Nlog2N) Tarjan算法LCA問題O(Na(N) + Q)O(N) 1RMQ算法 1RMQ問題O(N)-O(1)O(N) 注：N表示問題規(guī)模，Q表示詢問次數(shù) 第9頁/共85頁 第10頁/共85頁 我們以A序列為例建立樹T 第11頁/共85頁 1 將最小元素1作為根節(jié)點(diǎn) 左右分別建樹 第12頁/共85頁 1 10 右子樹只有一個(gè)結(jié)點(diǎn)，即10 第13頁/共85頁 1 10 左子樹有三個(gè)結(jié)點(diǎn)7、5、8 第14頁/共85頁 1 105 左子樹有三個(gè)結(jié)點(diǎn)7、5、8 將最小

3、元素5作為根節(jié)點(diǎn) 左右分別建樹 第15頁/共85頁 1 105 78 元素5的左右子樹都只有一個(gè) 結(jié)點(diǎn)，分別是7、8 第16頁/共85頁 1 105 78 這樣我們便得到了樹T 第17頁/共85頁 第18頁/共85頁 第19頁/共85頁 1 234 5 6 深度0 深度1 深度2 11252621341歐拉序列F ： 深度序列B：0 1 2 1 2 1 0 1 0 1 0 Pos (u)：1 2 8 10 3 5 第20頁/共85頁 第21頁/共85頁 第22頁/共85頁 一般RMQ問題 RMQ問題LCA問題 ST算法 Tarjan算法 RMQ算法 第23頁/共85頁 第24頁/共85頁 第2

4、5頁/共85頁 第26頁/共85頁 第27頁/共85頁 第28頁/共85頁 第29頁/共85頁 第30頁/共85頁 第31頁/共85頁 v u 第32頁/共85頁 v u p0 第33頁/共85頁 v u p0 第34頁/共85頁 第35頁/共85頁 第36頁/共85頁 第37頁/共85頁 第38頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 我們使用Kruskal算法生成上圖的最小生成森林，將所有邊 按照權(quán)值從小到大加入 第39頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 加入邊(1, 2)為樹邊 注意到Query(1, 2)的關(guān)鍵邊為(1,

5、 2) 第40頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 加入邊(1, 3)為樹邊 注意到Query(1|2, 3)的關(guān)鍵邊為(1, 3) 第41頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 加入邊(4, 6)為樹邊 注意到Query(4, 6)的關(guān)鍵邊為(4, 6) 第42頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 加入邊(5, 6)為樹邊 注意到Query(4|6, 5)的關(guān)鍵邊為(5, 6) 第43頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 加入邊(2, 3) 注意到已存在路徑(

6、2, 1) (1, 3)，所以(2, 3)非樹邊 第44頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 加入邊(3, 4)為樹邊 注意到Query(1|2|3,4|5|6)的關(guān)鍵邊為(3, 4) 第45頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 此時(shí)，我們已經(jīng)的到了最小生成森林T 更重要的是，我們也已經(jīng)得到了所有詢問的回答！ 第46頁/共85頁 第47頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 第48頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 第49頁/共85頁 1 2 3 4 5 6

7、1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 第50頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 第51頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 第52頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 第53頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 E1 第54頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10

8、V1V2 V3 V4 V5 V6 E1 E2 第55頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 E1 E2 E3 第56頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 E1 E2 E3 E4 第57頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 E1 E2 E3 E4 E5 第58頁/共85頁 1 2 3 4 5 6 1 5 2 6 7 3 4 10 V1V2 V3 V4 V5 V6 E1 E2 E3 E4 E5 第5

9、9頁/共85頁 第60頁/共85頁 第61頁/共85頁 第62頁/共85頁 第63頁/共85頁 第64頁/共85頁 第65頁/共85頁 第66頁/共85頁 第67頁/共85頁 第68頁/共85頁 第69頁/共85頁 第70頁/共85頁 第71頁/共85頁 ijA 2k 2k 第72頁/共85頁 l我們可以用O(N)的時(shí)間處理長(zhǎng)度為1的區(qū)間 l對(duì)于長(zhǎng)度為2k的區(qū)間的最小值，可以由兩個(gè)長(zhǎng) 度為2k-1的區(qū)間的最小值得到（如圖） 2k 2k-12k-1 第73頁/共85頁 第74頁/共85頁 u v p1 p2 v v 第75頁/共85頁 u p1 p2 正在遍歷 F(x) F(x) F(x) 第76頁/共85頁 u p1 p2 正在遍歷 第77頁/共85頁 u p1 p2 正在遍歷 F 第78頁/共85頁 注：此處F采用并查集實(shí)現(xiàn) 第79頁/共85頁 l以L = log2N / 2塊長(zhǎng)把B劃分為M = N / L段，記 錄第k塊的最小元素為BlockMin(k)，把M塊的最 小值組成序列Blocks，利用分塊思想，我們可 以把詢問分為兩個(gè)部分詢問： log2N / 2 BlockMin(1 ) BlockMin(M)