LCA與RMQ問題

1、 定義

LCA（Least Common Ancestors），即最近公共祖先，是指這樣一個問題：在有根樹中，找出某兩個結點u和v最近的公共祖先（另一種說法，離樹根最遠的公共祖先）。

 RMQ（Range Minimum/Maximum Query），即區間最值查詢，是指這樣一個問題：對于長度為n的數列A，回答若幹詢問RMQ（A,i,j）(i,j<=n)，傳回數列A中下标在i，j之間的最小/大值。這兩個問題是在實際應用中經常遇到的問題，本文介紹了目前解決這兩種問題的比較高效的算法。

再來個淺顯的說法：對于有根樹T的兩個結點u、v，最近公共祖先LCA(T,u,v)表示一個結點x，滿足x是u、v的祖先且x的深度盡可能大。另一種了解方式是把T了解為一個無向無環圖，而LCA(T,u,v)即u到v的最短路上深度最小的點。（這樣應該懂了吧）

再給出一個LCA的例子：

對于T=

V={1,2,3,4,5}

E={(1,2),(1,3),(3,4),(3,5)}

則有：

LCA(T,5,2)=1

LCA(T,3,4)=3

LCA(T,4,5)=3

2、 RMQ算法

RMQ問題是指：對于長度為n的數列A，回答若幹詢問RMQ(A,i,j)(i,j<=n)，傳回數列A中下标在[i,j]裡的最小值下标。下面是一個RMQ問題的例子：

對于數列：5,8,1,3,6,4,9,5,7 有：

RMQ(2,4)=3

RMQ(6,9)=6

其實RMQ問題與LCA問題的關系緊密，可以互相轉換，相應的求解算法也有異曲同工之妙。（嘿嘿。。。想想再往下看）

下面給出LCA問題向RMQ問題的轉化方法。

對樹進行深度優先周遊，每當周遊或回溯到某個結點時，将這個結點的深度存入數組E最後一位。同時記錄結點i在數組中第一次出現的位置(事實上就是進入結點i時記錄的位置)，記做R[i]。

如果結點E[i]的深度記做D[i]，易見，這時求LCA(T,u,v)，就等價于求 E[RMQ(D,R[u],R[v])]。

如果數列E[i]為：1,2,1,3,4,3,5,3,1

R[i]為：1,2,4,5,7

D[i]為：0,1,0,1,2,1,2,1,0

于是有：

LCA(T,5,2) = E[RMQ(D,R[2],R[5])] = E[RMQ(D,2,7)] = E[3] = 1

LCA(T,3,4) = E[RMQ(D,R[3],R[4])] = E[RMQ(D,4,5)] = E[4] = 3

LCA(T,4,5) = E[RMQ(D,R[4],R[5])] = E[RMQ(D,5,7)] = E[6] = 3

易知，轉化後得到的數列長度為樹的結點數的兩倍加一，是以轉化後的RMQ問題與LCA問題的同規模。

對于該RMQ問題，最容易想到的解決方案是周遊，複雜度是O(n)。但當資料量非常大且查詢很頻繁時，該算法也許會存在問題。

下面介紹了一種比較高效的線上算法（ST算法）解決這個問題。所謂線上算法，是指使用者每輸入一個查詢便馬上處理一個查詢。該算法一般用較長的時間做預處理，待資訊充足以後便可以用較少的時間回答每個查詢。ST（Sparse Table）算法是一個非常有名的線上處理RMQ問題的算法，它可以在O(nlogn)時間内進行預處理，然後在O(1)時間内回答每個查詢。

首先是預處理O（nlogn），用動态規劃（DP）解決。設A[i]是要求區間最值的數列，F[i, j]表示從第i個數起連續2^j個數中的最大值。例如數列3 2 4 5 6 8 1 2 9 7，F[1，0]表示第1個數起，長度為2^0=1的最大值，其實就是3這個數。 F[1，2]=5，F[1，3]=8，F[2，0]=2，F[2，1]=4……從這裡可以看出F[i,0]其實就等于A[i]。這樣，DP的狀态、初值都已經有了，剩下的就是狀态轉移方程。我們把F[i，j]平均分成兩段（因為f[i，j]一定是偶數個數字），從i到i+2^(j-1)-1為一段，i+2^(j-1)到i+2^j-1為一段(長度都為2^（j-1）)。用上例說明，當i=1，j=3時就是3,2,4,5 和 6,8,1,2這兩段。F[i，j]就是這兩段的最大值中的最大值。于是我們得到了動态規劃方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）。

然後是查詢。取k=[log2(j-i+1)]，則有：RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}。 舉例說明，要求區間[2，8]的最大值，就要把它分成[2,5]和[5,8]兩個區間，因為這兩個區間的最大值我們可以直接由f[2，2]和f[5，2]得到。

同樣，這樣的問題也可以用線段樹解決，算法複雜度為：O(N)~O(logN)。

但ST表可以O（nlogn）預處理，O（1）查詢。

3、 LCA算法

對于該問題，最容易想到的算法是分别從節點u和v回溯到根節點，擷取u和v到根節點的路徑P1，P2，其中P1和P2可以看成兩條單連結清單，這就轉換成常見的一道面試題：【判斷兩個單連結清單是否相交，如果相交，給出相交的第一個點。】。該算法總的複雜度是O（n）（其中n是樹節點個數）。

下面介紹了兩種比較高效的算法解決這個問題，其中一個是線上算法（DFS+ST），另一個是離線算法（Tarjan算法）。

線上算法DFS+ST描述(思想是：将樹看成一個無向圖，u和v的公共祖先一定在u與v之間的最短路徑上)：

（1）DFS：從樹T的根開始，進行深度優先周遊（将樹T看成一個無向圖），并記錄下每次到達的頂點。第一個的結點是root(T)，每經過一條邊都記錄它的端點。由于每條邊恰好經過2次，是以一共記錄了2n-1個結點，用E[1, ... , 2n-1]來表示。

（2）計算R：用R[i]表示E數組中第一個值為i的元素下标，即如果R[u] < R[v]時，DFS通路的順序是E[R[u], R[u]+1, …, R[v]]。雖然其中包含u的後代，但深度最小的還是u與v的公共祖先。

（3）RMQ：當R[u] ≥ R[v]時，LCA[T, u, v] = RMQ(L, R[v], R[u])；否則LCA[T, u, v] = RMQ(L, R[u], R[v])，計算RMQ。

由于RMQ中使用的ST算法是線上算法，是以這個算法也是線上算法。

【舉例說明】

T=<V,E>，其中V={A,B,C,D,E,F,G},E={AB,AC,BD,BE,EF,EG},且A為樹根。則圖T的DFS結果為：A->B->D->B->E->F->E->G->E->B->A->C->A，要求D和G的最近公共祖先, 則LCA[T, D, G] = RMQ(L, R[D], R[G])= RMQ(L, 3, 8)，L中第4到7個元素的深度分别為：1,2,3,3，則深度最小的是B。

離線算法（Tarjan算法）描述：

所謂離線算法，是指首先讀入所有的詢問（求一次LCA叫做一次詢問），然後重新組織查詢處理順序以便得到更高效的處理方法。Tarjan算法是一個常見的用于解決LCA問題的離線算法，它結合了深度優先周遊和并查集，整個算法為線性處理時間。

Tarjan算法是基于并查集的，利用并查集優越的時空複雜度，可以實作LCA問題的O(n+Q)算法，這裡Q表示詢問 的次數。

同上一個算法一樣，Tarjan算法也要用到深度優先搜尋。

算法大體流程如下：對于新搜尋到的一個結點，首先建立由這個結點構成的集合，再對目前結點的每一個子樹進行搜尋，每搜尋完一棵子樹，則可确定子樹内的LCA詢問都已解決。其他的LCA詢問的結果必然在這個子樹之外，這時把子樹所形成的集合與目前結點的集合合并，并将目前結點設為這個集合的祖先。之後繼續搜尋下一棵子樹，直到目前結點的所有子樹搜尋完。這時把目前結點也設為已被檢查過的，同時可以處理有關目前結點的LCA詢問，如果有一個從目前結點到結點v的詢問，且v已被檢查過，則由于進行的是深度優先搜尋，目前結點與v的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包涵v的子樹一定已經搜尋過了，那麼這個最近公共祖先一定是v所在集合的祖先。

例子：

根據實作算法可以看出，隻有當某一棵子樹全部周遊處理完成後，才将該子樹的根節點标記為黑色（初始化是白色），假設程式按上面的樹形結構進行周遊，首先從節點1開始，然後遞歸處理根為2的子樹，當子樹2處理完畢後，節點2， 5， 6均為黑色；接着要回溯處理3子樹，首先被染黑的是節點7（因為節點7作為葉子不用深搜，直接處理），接着節點7就會檢視所有詢問(7, x)的節點對，假如存在(7, 5)，因為節點5已經被染黑，是以就可以斷定(7, 5)的最近公共祖先就是find(5).ancestor，即節點1（因為2子樹處理完畢後，子樹2和節點1進行了union，find(5)傳回了合并後的樹的根1，此時樹根的ancestor的值就是1）。有人會問如果沒有(7, 5)，而是有(5, 7)詢問對怎麼處理呢? 我們可以在程式初始化的時候做個技巧，将詢問對(a, b)和(b, a)全部存儲，這樣就能保證完整性。