最小公共祖先(_LCA_)問(wèn)題

1、最小公共祖先( LCA )問(wèn)題 poj1330,1986,1470-fuyuchang(cc)&internet 大綱n定義n將 LCA 問(wèn)題轉(zhuǎn)化為 RMQ 問(wèn)題nRMQ 的一般解法n1 RMQ 問(wèn)題的快速解法nRMQ 的快速解法LCA 最小公共祖先在樹T中，結(jié)點(diǎn)u和v的最小公共祖先是它們共有的、離根結(jié)點(diǎn)最遠(yuǎn)的那個(gè)祖先結(jié)點(diǎn)。LCAT(u,v)uvRMQ 區(qū)間最小詢問(wèn)詢問(wèn) RMQA(i,j) 返回的是數(shù)組Ai.j中最小元素的下標(biāo)。RMQA(i,j) 0163413 7191012 1 2RMQA(3,7) = 4A0A2A1A9A3 A4 A5 A6 A7A8時(shí)間復(fù)雜度標(biāo)記)n(g),n

2、(f預(yù)預(yù)處理時(shí)間處理時(shí)間單個(gè)詢問(wèn)處理時(shí)單個(gè)詢問(wèn)處理時(shí)間間LCA 一般的算法n對(duì)任意一對(duì)結(jié)點(diǎn)，分別找出它們到樹根的路徑，然后在這兩條路經(jīng)中找第一個(gè)公共的結(jié)點(diǎn)。 復(fù)雜度 = ) 1 (O),n(O3LCA普通算法的圖將 LCA 轉(zhuǎn)化為 RMQn如果有一個(gè)復(fù)雜度為 的 RMQ解法，那么就存在一個(gè)復(fù)雜度為 的LCA解法。 n變形 根據(jù)樹T構(gòu)造3個(gè)數(shù)組1. E1.2n-1：存放從樹根開始的Euler遍歷所經(jīng)過(guò)的結(jié)點(diǎn)編號(hào)。2. L1.2n-1：Li存放Ei結(jié)點(diǎn)在樹T中的深度。3. P1.n： Ri表示結(jié)點(diǎn)i在數(shù)組E中第一次出現(xiàn)的下標(biāo)。)(),(ngnf) 1 () 12(),() 12(OngnOnf8例

3、012369547下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18Eu: 0 1 2 1 3 1 0 4 0 5 6 5 7 8 7 5 9 5 0id: 0 1 2 1 2 1 0 1 0 1 2 1 2 3 2 1 2 1 0P: 0 1 2 4 7 9 10 12 13 16計(jì)算 LCAT(u,v)nEuler 遍歷過(guò)程中，夾在u和v第一次被訪問(wèn)中間的結(jié)點(diǎn)是ERu,Rv。n其中深度最小的結(jié)點(diǎn)的下標(biāo)是 RMQL(Ru,Rv)。nLCAT(u,v)的結(jié)果就是 ERMQL(Ru,Rv)。例 LCAT(6,9)0123695847E: 0 1 2

4、 1 3 1 0 4 0 5 6 5 7 8 7 5 9 5 0L: 0 1 2 1 2 1 0 1 0 1 2 1 2 3 2 1 2 1 0P: 0 1 2 4 7 9 10 12 13 16R6R9E10,16RMQL(10,16) = 11LCAT(6,9) = E11=5復(fù)雜度分析預(yù)處理預(yù)處理n數(shù)組構(gòu)造：O(n)。n根據(jù)假設(shè)，對(duì)數(shù)組 L 進(jìn)行預(yù)處理：f(2n-1)。詢問(wèn)處理詢問(wèn)處理n三個(gè)數(shù)組的訪問(wèn)： O(1)。n根據(jù)假設(shè)，對(duì)數(shù)組 L 進(jìn)行RMQ詢問(wèn)處理：g(2n-1)?？偣玻嚎偣玻?) 1 () 12(),() 12(OngnOnfRMQ-LCA在線算法部分代碼nbool visit

5、MAXNODE;nint oula2*MAXNODE,distMAXNODE,posMAXNODE,minrmq182*MAXNODE,idMAXNODE;nint n,m;nvoid add(int u, int v, int w)nn edgee.to = v;n edgee.w = w;n edgee.next = headu;n headu = e+;nnvoid init()n rst(head,-1);n rst(visit,false);n tmpdfn=0;n index=0;n e=0;nnvoid dfs(int u)n visitu=true;n int len;n in

6、t oulanum=+tmpdfn;n oula+index=oulanum;n posu=index;n idoulanum=u;n for(int i=headu;i!=-1;i=edgei.next)n int next=edgei.to;n if(!visitnext)n /visitnext=true; dfs(next);n oula+index=oulanum;n n n return ;nRMQ-LCA在線算法部分代碼nint getmin(int l, int r)nint limit=(int)(log(r-l+1)*1.0)/log(2.0);n return min(m

7、inrmqlimitl,minrmqlimitr-(1limit)+1);nnvoid RMQ(int len,int *oularmq)n int limit,j;n limit=(int)(log(len*1.0) / log(2.0);n forle(i,1,len)minrmq0i=oularmqi;n forle(i,1,limit)n for(j=1;(j+(1i)-1=len;j+)n minrmqij=min(minrmqi-1j,minrmqi-1j+(1posr)cc=l,l=r,r=cc;n int ans=getmin(posl,posr);n return idans

8、;nTarjan-LCA離線算法n 核心思想：對(duì)于最近公共祖先問(wèn)題，核心思想：對(duì)于最近公共祖先問(wèn)題，我們先來(lái)看這樣一個(gè)性質(zhì)，我們先來(lái)看這樣一個(gè)性質(zhì)，當(dāng)兩個(gè)節(jié)點(diǎn)當(dāng)兩個(gè)節(jié)點(diǎn)（u，v）的最近公共祖先是）的最近公共祖先是x時(shí)，那么我時(shí)，那么我們可以確定的說(shuō)，當(dāng)進(jìn)行后序遍歷的時(shí)們可以確定的說(shuō)，當(dāng)進(jìn)行后序遍歷的時(shí)候，必然先訪問(wèn)完候，必然先訪問(wèn)完x的所有子樹，然后才的所有子樹，然后才會(huì)返回到會(huì)返回到x所在的節(jié)點(diǎn)。所在的節(jié)點(diǎn)。這個(gè)性質(zhì)就是我這個(gè)性質(zhì)就是我們使用們使用Tarjan算法解決最近公共祖先問(wèn)算法解決最近公共祖先問(wèn)題的核心思想。題的核心思想。Tarjan-LCA離線算法n 大概流程：每搜索完一棵子樹，則

9、可確定子樹內(nèi)的LCA詢問(wèn)都已經(jīng)解決。其他的LCA詢問(wèn)的結(jié)果由于沒訪問(wèn)到，在子樹之外，這時(shí)把子樹的集合和當(dāng)前的節(jié)點(diǎn)的集合合并，并將當(dāng)前節(jié)點(diǎn)設(shè)為這個(gè)集合的公共祖先。之后繼續(xù)搜索下一個(gè)子樹，直到當(dāng)前節(jié)點(diǎn)的所有子樹搜索完。這時(shí)把當(dāng)前節(jié)點(diǎn)也設(shè)為被訪問(wèn)過(guò)，同時(shí)可以處理有關(guān)當(dāng)前節(jié)點(diǎn)的LCA詢問(wèn)，如果有一個(gè)從當(dāng)前節(jié)點(diǎn)到節(jié)點(diǎn)V的詢問(wèn)，且V已被檢查過(guò)，則由于進(jìn)行的是DFS，當(dāng)前節(jié)點(diǎn)與V的最近公共祖先一定還沒有被檢查，而這個(gè)最近公共祖先的包含V的子樹一定已經(jīng)搜索過(guò)了，那么這個(gè)最近公共祖先一定是V所在集合的祖先Tarjan-LCA離線算法部分代碼nvoid init()n rst(visit,0);n rst(deg

10、,0);n forle(i,1,n)fatheri=i;n forle(i,1,n)n edgei.clear();n n rst(quesion,0);n rst(cnt,0);nnint getfather(int k)n if(fatherk=k)return fatherk;n fatherk=getfather(fatherk);n return fatherk;nnforl(i,0,n)n scanf(%d:(%d),&x,&m);n while(m-)n scanf(%d,&y);n edgex.push_back(y);n degy+;n n nvoid

11、 LCA(int u)n fatheru=u;n int k;n int len;n for(k=0,len=edgeu.size();klen;k+)n int yy=edgeuk;n LCA(yy);n fatheryy=u;n n visitu=true;n for(int i=1;i=n;i+)n if(visiti&quesionui)n int fa=getfather(i);n cntfa+=quesionui;n quesionui=quesioniu=0;n n n return;nRMQ 的一般解法n從現(xiàn)在開始，主要研究 RMQ 問(wèn)題。n對(duì)每一對(duì)結(jié)點(diǎn)都預(yù)先求出 RM

12、Q 的解 -n改進(jìn)后使用一般的動(dòng)態(tài)規(guī)劃 - ) 1 (),(3OnO) 1 (),(2OnORMQ 的稀疏表(Sparse Table)算法預(yù)處理預(yù)處理 n 計(jì)算矩陣n n時(shí)間：O(nlogn)。a1.anii+2j-1i+2j-1-1)lognj1 n,i(1 jMi,min) 12,(,12kAiiRMQjiMjikijA 1,2Mi Otherwise 1- jMi, 1,2AMi1- jAMi, ,1 - j1 - jjjjiMRMQ 的稀疏表(Sparse Table)算法RMQ(i,j)詢問(wèn)處理詢問(wèn)處理n n n時(shí)間：O(1)。n總復(fù)雜度： a1an.ij2k elements2k

13、 elements1ij2rmaxkrk, 12jM Otherwiseki,M k, 12jMAk, iMA) j , i (RMQkk) 1 (O),nlogn(O1 RMQ 分段 .B0B2n/lognBi.A .A0A2n/lognAiA：每一段的最小值B：此段最小值的下標(biāo)nlog21 n log2n 段，每段的大小是分成nA的大小 = 2n / logn。nST_預(yù)處理(A) nST(A)=1 RMQ 處理A)(log)loglog2(log2n log2nlogn log2n nOnnnn) 1 (O),n(O1 RMQ 詢問(wèn)處理RMQ(i,j) 詢問(wèn)處理詢問(wèn)處理n需要計(jì)算以下這些

14、值：1. 從i到它所在段的末尾，這些數(shù)中間的最小值。2. 對(duì)A中夾在i和j分別所在的段之間的所有段的最小值。3. 從j所在段的起始到j(luò)，這些數(shù)中間的最小值。 .AiAj 1 2 31 RMQ 單段的一般處理單段的單段的ST 預(yù)處理預(yù)處理每一段所有段 .AiAj 1 2 3)nloglogn(logOn log21log n log21 )nloglogn(O觀察如果兩個(gè)數(shù)列X和Y有 CYiXi ,i 34 6 5 5 4 5 6 4 5A0A2A1A9A3 A4 A5 A6 A7 A8 0132 2 1 2 3 1 2A0A2A1A9A3 A4 A5 A6 A7A8+1-1-1-1+1+1-1

15、+1 +1),(),( , jiRMQjiRMQjiYX1 RMQ 單段的特殊處理n每段大小 = n每段的1序列長(zhǎng)度 = n可能1序列的種數(shù) =n預(yù)處理所有的1序列 =n確定每一段所使用的1序列 = O(n)n總的時(shí)間復(fù)雜度 =nlog211log21nnn2121log21nnO2log) 1 (O),n(O一般 RMQ 問(wèn)題n將 RMQ 轉(zhuǎn)化為 LCA斷言：n如果有一個(gè)復(fù)雜度為 的 LCA解法，那么就存在一個(gè)復(fù)雜度為 的RMQ解法。) 1 (O),n(O) 1 (O),n(O笛卡爾樹(Cartesian Tree)10163426 71910122522A0A2A1A9A3 A4 A5 A

16、6 A7A8n笛卡爾樹的樹根是數(shù)組中的最小元素。n每個(gè)結(jié)點(diǎn)記錄這個(gè)最小值元素的下標(biāo)。n這個(gè)元素將數(shù)組分成兩段，遞歸定義構(gòu)造笛卡爾樹。笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A846笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8476笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84769笛卡爾樹10163426 71910122522A0A2A1A9

17、A3 A4 A5 A6 A7A847698笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8457698笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84057698笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84021357698線性時(shí)間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7 A8n設(shè)Ci是 A0,i的笛卡爾樹。n第 i+1 個(gè)結(jié)點(diǎn)一定屬于 Ci+1 最右側(cè)的那條路徑。n從 Ci 的最右側(cè)路徑

18、由下往上找，直到發(fā)現(xiàn)第 i+1 個(gè)結(jié)點(diǎn)可以放的位置。n由于每個(gè)結(jié)點(diǎn)只進(jìn)入和離開最右側(cè)路徑至多一次，所以這個(gè)算法的時(shí)間復(fù)雜度是O(n)的。線性時(shí)間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8010線性時(shí)間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8011025線性時(shí)間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A802110222534線性時(shí)間構(gòu)造笛卡爾樹101626 71910122522A0A2A1A9A3 A4 A5 A6 A7A80213 3 7343410222534線性時(shí)間構(gòu)造笛卡爾樹10163426 71910122