夜深人靜寫算法（6）：最近公共祖先

一、引例

1、樹-結點間最短距離
【例題1】給定一棵n(n <= 100000)個結點的樹，以及m(m <= 100000)條詢問(u, v),對于每條詢問，求u和v的最短距離？

我們知道，一個普通的無向圖求兩點間最短距離可以采用單源最短路，將時間復雜度大致控制在O(nlogn)，但是當詢問足夠多的時候，這并不是一個高效的算法。從樹的性質可知，樹上任意兩點間有且僅有一條簡單路徑（路徑上沒有重點和重邊），所以樹上任意兩點間的最短距離其實就是這條簡單路徑的長度。如圖一-1-1所示，要求u到v的距離，我們需要知道紅色路徑A(u->r），藍色路徑B(v->r)，紅藍公共路徑C(a->r)，那么u->v的路徑顯然就可以通過A、B、C三者的長度計算出來，令dist[x]表示從x到樹根r的簡單路徑的長度，則u到v的距離可以表示成如下：dist[u] + dist[v] – dist[a]。

那么問題來了，a是什么，我們來看a->r路徑上的所有結點既是u的祖先，也是v的祖先，所以我們給它們一個定義稱為公共祖先（Common Ancestors），而a作為深度最深的祖先，或者說離u和v最近的，我們稱它為最近公共祖先（Lowest Common Ancestors），簡稱LCA。

圖一-1-1

二、LCA（最近公共祖先）

1、樸素算法
于是求樹上兩點間的距離轉化成了求兩個結點的最近公共祖先問題上來了，最容易想到的辦法是將u->r和v->r的兩條路徑通過遞歸生成出來，并且逆序保存，然后比較兩條路徑的公共前綴路徑，顯然公共前綴路徑的尾結點就是u和v的最近公共祖先，但是這個算法在樹退化成鏈的時候達到最壞復雜度O(n)，并不可行。

2、步進法
對于兩個結點u和v，假設它們的最近公共祖先為lca(u, v)，用depth[x]表示x這個結點的深度，pre[x]表示x的父結點。那么很顯然，有depth[ lca(u, v) ] <= min{depth[u], depth[v]}，通過這樣一個性質，我們可以很容易得出一個算法：
1) 當depth[u] < depth[v]時，lca(u, v) = lca(u, pre[v]);
2) 當depth[u] > depth[v]時，lca(u, v) = lca(pre[u], v);
利用以上兩個條件，可以將u和v不斷向根進行步進，遞歸求解，直到u == v時，這里的u或v就是原先要求的(u, v)的最近公共祖先。

3、記憶化步進法
【例題2】如圖二-3-1的網絡拓撲樹，給定兩個客戶端(x, y)，需要找到一個離他們最近的服務器來處理兩個客戶端的交互，客戶端和服務端數量小于等于1000，但是詢問數Q <= 10^8。

圖二-3-1

這是一個典型的LCA問題，并且詢問很多，還有一個特點是總的樹結點樹并不是很多，所以在步進法計算LCA的時候，可能會遇到很多重復的計算，具體是指計算lca(u, v)的時候可能在某次查詢的時候已經被計算過了，那么我們可以把這個二元組預先存在數組中，即lca[u][v]，這樣做可以避免多次查詢中遇到的冗余計算。但同時也帶來一個問題，就是空間復雜度是O(n^2)，對于n = 100000的情況下內存已經吃不消了，記憶化步進法只適用于n在千量級的情況。

4、tarjan算法
tarjan算法采用深度優先搜索遞歸計算結點(u, v)的LCA。具體的思想是在搜索過程中將一棵樹進行分類，分類如下：
a.以結點x為根的子樹作為a類結點；
b.以pre[x]為根的子樹去掉a類結點，為b類結點；
c.以pre[ pre[x] ]為根的子樹并且去掉a、b兩類，為c類結點；依此類推…

圖二-4-1

如圖二-4-1所示，對這棵樹進行深度優先搜索，深灰色結點（之所以不用黑色是因為線條也是黑的）表示以該結點為根的子樹已經盡數訪問完畢；淺灰色結點表示該結點為根的子樹正在進行訪問，且尚未訪問完畢；白色結點表示以該結點為根的子樹還沒開始訪問。圖中紅色圈出的部分為上文提到的a類結點；黃色圈出的部分為b類結點；藍色為c類結點；綠色為d類結點，以此類推，不同的顏色屬于不同的集合。所謂一圖在手，勝過萬語千言，從圖中很容易就能看出，x和所有綠色結點的LCA都為pre[pre[pre[x]]]，即x的曾祖父結點；和所有藍色結點的LCA都為pre[pre[x]]，即x的祖父結點；和所有黃色結點的LCA都為pre[x]，即x的父結點。

可能有人對這里集合的概念表示不理解，舉個例子就能明白了，我們還是沿用上圖，將圖上的結點進行編號，如圖二-4-2所示，可以得到其中三個集合為：
B = {8,13} C = {4,7,11,12,16} D = {1,2,3,5,6,9,10,14,15}
每個集合對應一棵子樹，按照tarjan算法的思路，當給定任意一個結點，我們需要得到這個結點所在集合對應的子樹的根結點，這里分兩步走：
1) 找到結點對應的集合；
2）找到集合的根；

第2)步可以預先將值保存在數組中，但是集合不像數字，不能作為數組的下標。而我們注意到這里的集合都是互不相交的，這一點是非常關鍵的，這就意味著我們可以用一個集合中的元素來作為這個集合的“代表元”。假設B的代表元為13，C的代表元為7，D的代表元為5，用ancestor數組來存儲集合的根結點，則有ancestor[13] = 8, ancestor[7] = 4, ancestor[5] = 1，于是第2)步就能在O(1)的時間內完成了。
第1)步其實可以描述成給定一個結點，求該結點所在集合的代表元。這里先不討論實現，因為這個操作會在第三節并查集中花很長的篇幅來講。

圖二-4-2

對集合有一定了解后，讓我們最后總結下這個算法究竟是如何實現的。
1) 初始化所有結點顏色colors[i] = 0，對樹T進行深度優先搜索；
2) 訪問到結點u時，將u單獨作為一個集合，并且令ancestor[u] = u，即這個集合的根結點為u，然后跳轉到3)；
3) 訪問u的所有子結點v，遞歸執行2)，當v所在子樹結點全部訪問完畢后，將v所在集合和u所在集合合并（執行merge(u, v)），并且令新的集合的祖先為u（執行ancestor[find(u)] = u）；
4) 當u所在子樹結點全部訪問完畢后，置colors[u] = 1，枚舉所有和u有關的詢問：(u, v)，如果colors[v]等于1，那么記錄u和v的最近公共祖先為ancestor[ find(v) ]；

這里有兩個神奇的函數，merge(u, v)和find(u)，其中merge(u, v)表示合并u和v所在的兩個集合，find(u)則表示找到u所在集合的代表元。如果對這個算法已經有一定的認知，那么趁熱打鐵，來看下偽代碼是如何實現的。

void LCA_Tarjan(int u) { 
    make_set(u);                               // 注釋1
    ancestor[ find(u) ] = u;                   // 注釋2
    for(int i = 0; i < edge[u].size(); i++) {  // 注釋3
        int v = edge[u][i].v; 
        LCA_Tarjan(v);                         // 注釋4
        merge(u, v);                           // 注釋5
        ancestor[ find(u) ] = u;               // 注釋6
    }
    colors[u] = 1;                             // 注釋7
    for(int i = 0; i < lcaInfo[u].size(); i++) {
        int v = lcaInfo[u][i].v;
        if(colors[v]) {                        // 注釋8
            lcaDataAns[ lcaInfo[u][i].idx ].lca = ancestor[ find(v) ];
        }
    }
}

注釋1:創建一個集合，集合中只有一個元素u，即{ u }
注釋2:因為u所在集合只有一個元素，所以也可以寫成ancestor[u] = u
注釋3:edge[u][0...size-1]存儲的是u的直接子結點
注釋4:遞歸計算u的所有直接子結點v
注釋5:回溯的時候進行集合合并，將以v為根的子樹和u所在集合進行合并
注釋6:對合并完的集合設置集合對應子樹的根結點，find(u)為該集合的代表元
注釋7:u為根的子樹訪問完畢，設置結點顏色
注釋8:枚舉所有和u相關的詢問(u, v)，如果以v為根的子樹已經訪問過，那么ancestor[find(v)]肯定已經計算出來，并且必定是u和v的LCA

tarjan算法的時間復雜度為O(n+q)，其中n為結點個數，q為詢問對(u, v)的個數。但是在進行深搜之前首先需要知道所有的詢問對，所以是一個離線算法，不能實時進行計算，局限性較大。

【例題3】在一個可視化的界面上的一棵樹，選中某些結點，然后要求在文件中保存一棵最小的子樹，使得這棵子樹包含所有這些選中的結點。
doubly算這個是實際文件保存中比較經典的問題，我們可以選擇兩個結點求出LCA，然后用這個LCA再和兩一個點求LCA，以此類推…n個結點經過n-1次迭代就能求出n個結點的LCA，這個LCA就是要保存的子樹的根結點了。

5、doubly算法

doubly算法（倍增法）是在線算法，可以實時計算任意兩點間的LCA，并且每次計算時間復雜度是O(1)的。

該算法同樣也是基于深度優先搜索的，遍歷的時候從根結點開始遍歷，將遍歷的邊保存下來，對于一棵n個結點的樹來說總共有n-1條邊，那么遍歷的時候需要保存2*(n-1)條邊（自頂向下的邊，以及回溯時的邊，所以總共兩倍的邊），這些邊順序存儲后相鄰兩條邊的首尾結點必定是一致的，所以可以壓縮到一個一維數組E中，數組的長度為2*(n-1)+1，然后建立一個輔助數組D，長度和E一致，記錄的是E數組中對應結點的深度，這個在遍歷的時候可以一并保存，然后再用一個輔助數組I[i]來保存i這個結點在E數組中第一次出現的下標。至此，初始化工作就算完畢了。

那么當詢問兩個結點u和v的LCA時，我們首先通過輔助數組I獲取兩個結點在D數組中的位置，即I[u]和I[v]，不妨設I[u] <= I[v],那么在D數組中的某個深度序列D[ I[u], I[u]+1, … I[v]-1, I[v] ]，其實表示的是從u到v的路徑上每個結點的深度，而之前我們已經知道樹上任意兩個結點的簡單路徑有且僅有一條，并且路徑上深度最小的點就是u和v的LCA，所以問題轉化成了求D[ I[u], I[u]+1, … I[v]-1, I[v] ]的最小值，找到最小值所在下標后再到E數組索引得到結點的值就是u和v的LCA了。

圖二-5-1

如圖二-5-1為n = 7個結點的一棵樹，其中0為根結點，6條邊分別為(0,5)(5,2)(2,4)(0,3)(3,1)(3,6)。注意這里的邊是有向邊，即一定是父結點指向子結點，如果給定的是無向邊，需要預先進行處理。如右圖，從根結點進行遍歷，其中紅色的邊為自頂向下的邊，綠色的邊為回溯邊，回溯邊一定是子結點指向父結點的，藍色的小數字代表邊的遍歷順序，即第幾條邊，將所有的邊串起來就變成這樣了：
(0,5) -> (5,2) -> (2,4) -> (4,2) -> (2,5) -> (5,0) -> (0,3) -> (3,1) -> (1,3) -> (3,6) -> (6,3) -> (3,0)

然后我們將這些邊壓縮到數組E中，得到：
E[1 ... 2n-1] = 0 5 2 4 2 5 0 3 1 3 6 3 0

對數組E中對應的結點在樹上的深度記錄在數組D中，得到：
D[1 ... 2n-1] = 0 1 2 3 2 1 0 1 2 1 2 1 0

再將每個結點在數組E中第一次出現的位置記錄在數組I中，得到：
I[0 ... n-1] = 1 9 3 8 4 2 11
注意：這里的數組E和D都是1-based，而I數組是0-based，這個是個人習慣，可自行約定，不必糾結。

根據LCA的性質，有LCA(x, y) = E[ Min_Index( D, I[x], I[y] ) ]，其中Min_Index(Array, i, j)表示Array數組中[i, j]區間內的最小值對應的下標，那么問題的難點其實就是在于求Min_Index(Array, i, j)了，這個問題就是經典的區間最值問題，最常見的可以采用線段樹求解，建好樹后單次查詢的時間復雜度為O(logn)，當然還有一種更加高效的算法，查詢復雜度可以達到嚴格的O(1)，這就是第四節要討論的RMQ問題。
由于tarjan算法中還有一個有關集合操作的遺留問題尚未介紹，這里先來看史上最輕量級的數據結構——并查集。

三、并查集

1、”并”和”查”
并查集是一種處理不相交集合的數據結構，它支持兩種操作：
1）合并操作merge(x, y)。即合并兩個原本不相交的集合，此所謂“并”。
2）查找操作find(x)。即檢索某一個元素屬于哪個集合，此所謂“查”。

講個簡單的故事來加深對并查集的理解，這個故事要追溯到北宋年間。話說北宋時期，朝綱敗壞，奸臣當道，名不聊生。又有外侮遼軍大舉南下，于是眾多能人異士群起而反，各大武林門派同仇敵愾，共抗遼賊，為首的自然是中原武林第一大幫-丐幫，其幫主乃萬軍叢中取上將首級猶如探囊取物、泰山崩于前而面不改色的北喬峰；與其齊名的空有一腔抱負、壯志未酬的南慕容帶領的慕容世家；當然也少不了天下武功的鼻祖-少林，以及一些小幫派，如逍遙派、靈鷲宮、無量劍、神農教等等。我們將每個門派（幫派）作為一個集合，從中選出一個代表作為這個集合的標識，姑且認為門派（幫派）的掌門（幫主）就是這個代表。
作者有幸成了“抗遼聯盟”的統計員，統計員只有一個工作，就是接收一條條同門數據，然后統計共有多少個門派，好進行分派部署。同門數據的格式為(x, y)，表示x和y屬于同一個門派，接收到一條數據，需要對x所在的群體和y的群體進行合并，當統計完所有數據后有多少個集合就代表多少個門派。

這個問題其實隱含了兩個操作：1、查找a和b是否已經在同一個門派；2、如果兩個人的門派不一致，則合并這兩個人所在集合的兩堆人。分別對應了并查集的查找和合并操作。
如圖三-1-1所示，分別表示丐幫、少林、逍遙、大理段氏四個集合。

圖三-1-1

2、樸素算法
接下來來討論下并查集的樸素實現，既然是樸素實現，當然是越樸素越好。樸素的只需要一個數組就能表示集合，我們用set[i]表示i所在的集合，這樣查找操作的時間復雜度就能通過下標索引達到O(1)（可以把set數組理解成哈希表）；合并x和y的操作需要判斷set[x]和set[y]是否相等，如果不相等，需要將所有滿足set[i]等于set[x]的set[i]變成set[y]，由于這里需要遍歷set[i]，所以時間復雜度為O(n)。圖三-2-1展示了樸素算法的一個例子，該數組一共記錄了四個集合，并且用每個集合的最小數字作為該集合的標識。

圖三-2-1

給出樸素算法的偽代碼如下：

int find (int x) {
    return set[x];
}
void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        for(int i = 1; i <= n; i++) {
            if( set[i] == rx ) set[i] = ry;
        }
    }
}

初始化set[i] = i,每次得到一組數據(x, y),就執行merge(x, y)，統計完所有數據后，對set數組進行一次線掃，就能統計出總共有多少個門派。

3、森林實現
由于樸素實現合并操作的時間復雜度太高，在人數很多的情況下，效率上非常吃虧，如果有n次合并操作，那么總的時間復雜度就是O(n^2)。所以我們將集合的表示進行一定的優化，將一個個集合用樹的形式來組織，多個集合就組成了一個森林。用pre[i]表示i在集合樹上的父結點，當pre[i]等于i時，則表示i為這棵集合樹的根結點。那么顯而易見的，對于合并操作(x, y)，只需要查找x和y在各自集合樹的根結點rx和ry，如果rx和ry不相等，則將rx設為ry的父結點，即令pre[ry] = rx。查找操作更加簡單，只要順著父結點一直找到根結點，就找到了該結點所在的集合。初始化pre[i] = i，即表示森林中有n棵一個結點的樹。如圖三-3-1為合并x,y所在集合的操作。

圖三-3-1

給出森林實現的偽代碼如下：

int find (int x) {
    return x == pre[x] ? x : find(pre[x]);
}
void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    pre[ry] = rx;
}

代碼量較樸素算法減少了不少，那時間復雜度呢？仔細觀察，不難發現兩個操作的時間復雜度其實是一樣的，瓶頸都在查找操作上，來看一個簡單的例子。

【例題3】因為天下武功出少林，所以很多人都想加入少林習武，令少林寺的編號為1。然后給定m(m <= 100000)組數據(x, y)，表示x和y結成朋友，當x或y等于1時，表示另一個不等于1的人帶領他的朋友一起加入少林，已知總人數n，求最后少林寺來了多少人。

一個最基礎的并查集操作，對于每條數據執行merge(x, y)即可，最后一次線性掃描統計1所在集合的人數的個數，但是對于極限情況，還是會退化成O(n)的查找，如圖三-3-2所示，每次合并都是一條鏈合并到一個結點上，使得原本的樹退化成了鏈，合并本身是O(1)的，但是在合并前的查找根結點的過程中已經是O(n)的了，為了避免集合成鏈的情況，需要進行啟發式合并。

圖三-3-2

4、啟發式合并
啟發式合并是為了解決合并過程中樹退化成鏈的情況，用depth[i]表示根為i的樹的最大深度，合并ra和rb時，采用最大深度小的向最大深度大的進行合并，如果兩棵樹的最大深度一樣，則隨便選擇一個作為根，并且將根的最大深度depth自增1，這樣做的好處是在n次操作后，任何一棵集合樹的最大深度都不會超過log(n)，所以使得查找的復雜度降為O( log(n) ）。
給出啟發式合并的偽代碼如下：

int find (int x) {
    return x == pre[x] ? x : find(pre[x]);
}
int merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        if( depth[rx] == depth[ry] ) {
            pre[ry] = rx;
            depth[rx]++;
        }else if( depth[rx] < depth[ry] ) {
            pre[rx] = ry;
        }else {
            pre[ry] = rx;
        }
    }
}

啟發式合并的查找操作不變，合并操作引入了depth數組，并且在合并過程中即時更新。

5、路徑壓縮
【例題4】n(n <= 100000)個門派編號為1-n，經過m(m <= 100000)次江湖上的血雨腥風，不斷產生門派吞并，每次吞并可以表示成(x, y)，即x吞并了y，最后問從前往后數還存在的編號第k大的那個門派的編號。

啟發式合并通過改善合并操作提高了效率，但是這個問題的合并是有向的，即一定是y向x合并，所以無法采用按深度的啟發式合并，那么是否有辦法優化查找操作來改善效率呢？答案是一定的，我們可以在結點x找到樹根rx的時候，將x到rx路徑上的點的父結點都設置為rx，這樣做并不會改變原有的集合關系，如圖三-5-1所示。

圖三-5-1

由于每次查找過程中都對路徑進行了壓縮，使得任何時候樹的深度都是小于4的，從而查找操作可以認為是常數時間。
當然，如果合并是無向的同樣可以采用路徑壓縮，這樣做會導致樹的深度可能時刻在變化，所以啟發式合并的啟發值不能采用樹的深度，可以通過一個rank值來進行合并，rank值初始為0，當兩棵樹進行合并時，如果rank值相同，隨便選一棵樹的根作為新根進行合并，rank值+1；否則rank小的向大的合并，rank值保持不變。

給出路徑壓縮的偽代碼如下：

int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}
int merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        if( rank[rx] == rank[ry] ) {
            pre[ry] = rx;
            rank[rx]++;
        }else if( rank[rx] < rank[ry] ) {
            pre[rx] = ry;
        }else {
            pre[ry] = rx;
        }
    }
}

仔細觀察不難發現，路徑壓縮版本的find和merge操作與啟發式合并的版本除了紅色標注部分，其它完全相同（只是merge函數中depth變量名換成了rank），find函數中的賦值操作（紅色部分代碼）很好地詮釋了深度優先搜索在回溯時的完美表現，find函數的返回值一定是這棵集合樹的根結點root，回溯的時候會經過從x到root的路徑，通過這一步賦值可以很輕松的將該路徑上所有結點的父結點都設為根結點root。

6、元素刪除
【例題5】話說有人加入少林，當然也有人還俗，虛竹就是個很好的例子，還俗后加入了逍遙派，這就是所謂的集合元素的刪除。

并查集的刪除操作可以描述成：在某個集合中，將某個元素孤立出來成為一個只有它本身的新的集合。這步操作不能破壞原有的樹結構，單純“拆”樹是不現實的，如圖三-6-1所示,是我們的美好預期，但是事實上并做不到，因為在并查集的數據結構中只記錄了x的父親，而未記錄x的子結點，沒辦法改變x子結點的父結點。

圖三-6-1

而且就算是記錄了子結點，每次刪除操作最壞情況會更新n個子結點的父結點，使得刪除操作的復雜度退化成O(n)，還有一個問題就是x本身如果就是根結點，那么一旦x刪除，它的子結點就會妻離子散，家破人亡，需要重新建立關系，越想越復雜。

所以，及時制止記錄子結點的想法，采用一種新的思維——二次哈希法（ReHash），對于每個結點都有一個哈希值，在進行查找之前需要將x轉化成它的哈希值HASH[x]，那么在進行刪除的時候，只要將x的哈希值進行改變，變成一個從來沒有出現過的值（可以采用一個計數器來實現這一步），然后對新的值建立集合，因為只有它一個元素，所以必定是一個新的集合。這樣做可以保證每次刪除操作的時間復雜度都是O(1)的，而且不會破壞原有樹結構，唯一的一個缺點就是每刪除一個結點其實是多申請了一塊內存，如果刪除操作無限制，那么內存會無限增長。

四、RMQ

1、樸素算法
RMQ (Range Minimum/Maximum Query)問題是指：對于長度為n的數列Array，回答若干詢問RMQ(Array,i,j)(i,j<=n)，返回數列Array中下標在i,j里的最小(大）值（或者最小（大）值所在的下標），也就是說，RMQ問題是指求區間最值的問題。
樸素算法就是枚舉區間的值進行大小判定，如果長度為n的數組，詢問個數為q，那么算法的時間復雜度為O(qn)。

2、線段樹（簡介）
線段樹是一種二叉搜索樹，它的每個結點都保存一個區間[l, r]，如果當l等r時，表示該結點是一個葉子結點；否則它必定有兩個子結點，兩個子結點保存的區間分別為[l, mid]和[mid+1, r],其中mid = (l+r)/2的下整，利用二分（分治）的思想將一個長度為n的區間分割成一系列單位區間（葉子區間）。

線段樹的每個結點都可以保存一些信息，最經典的應用就是區間最值，可以在結點上保存該結點對應區間[l, r]上的最值，每次詢問[A, B]區間最值時將區間[A, B]進行劃分，劃分成一些區間的并集，并且集合中的區間必定都能在線段樹結點上一一對應，可以證明一定存在這樣一個劃分，并且劃分的集合個數不會超過logn，從而使得每次查詢的時間復雜度能夠保證在O(logn)。

由于線段樹還有很多經典應用，不想在這篇文章快要結束的時候草草了事，所以在標題上加了“簡介”二字，等到日后有時間再詳細介紹吧。

3、ST算法
ST（Sparse Table）算法是基于動態規劃的，用f[i][j]表示區間起點為j長度為2^i的區間內的最小值所在下標，通俗的說，就是區間[j, j + 2^i)的區間內的最小值的下標。

從定義可知，這種表示法的區間長度一定是2的冪，所以除了單位區間(長度為1的區間)以外，任意一個區間都能夠分成兩份，并且同樣可以用這種表示法進行表示，[j, j + 2^i)的區間可以分成[j, j+2^(i-1))和[j + 2^i)，于是可以列出狀態轉移方程為： f[i][j] = RMQ( f[i-1][j], f[i-1][j+2^(i-1)] )。 f[m][n]的狀態數目為n*m = nlogn，每次狀態轉移耗時O(1)，所以預處理總時間為O(nlogn)。

原數組長度為n，當[j, j + 2^i)區間右端點 j + 2^i - 1 > n時如何處理？在狀態轉移方程中只有一個地方會下標越界，所以當越界的時候狀態轉移只有一個方向，即當j + 2^(i-1) > n 時，f[i][j] = f[i-1][j]。

求解f[i][j]的代碼就不給出了，只需要兩層循環的狀態轉移就搞定了。

f[i][j]的計算只是做了一步預處理，但是我們在詢問的時候，不能保證每個詢問區間長度都是2的冪，如何利用預處理出來的值計算任何長度區間的值就是我們接下來要解決的問題。

首先只考慮區間長度大于1的情況（區間長度為1的情況最小值就等于它本身），給定任意區間[a, b] (1 <= a < b <= n)，必定可以找到兩個區間X和Y，它們的并是[a, b]，并且區間X的左端點是a，區間Y的右端點是b，而且兩個區間長度相當，且都是2的冪，如圖所示：

圖四-3-1

設區間長度為2^k，則X表示的區間為[a, a + 2^k)，Y表示的區間為(b - 2^k, b]，則需要滿足一個條件就是X的右端點必須大于等于Y的左端點減一，即 a+2^k-1 >= b-2^k，則2^(k+1) >= (b-a+1), 兩邊取對數（以2為底），得 k+1 >= lg(b-a+1)，則k >= lg(b-a+1) – 1，k只要需要取最小的滿足條件的整數即可( lg(x)代表以2為底x的對數 )。

仔細觀察發現b-a+1正好為區間[a, b]的長度len，所以只要區間長度一定，k就能在常數時間內求出來。而區間長度只有n種情況，所以k可以通過預處理進行預存。

當lg(len)為整數時，k 取 lg(len)-1，否則k為 lg(len)-1 的上整（并且只有當len為2的冪時，lg(len)才為整數）。
代碼如下：

for(i = 1, k = 0; i <= n; i++) {
    lg2K[i] = k - 1;
    if((1<<k) == i) k++;
}
int RMQ_Query(ValueType val[], int (*f)[MAXN], int a, int b) {
    if(a == b) return a;
    int k = lg2K[ abs(b-a) + 1 ];
    int x = f[k][a], y = f[k][b-(1<<k)+1];
    return val[x] < val[y] ? x : y;
}

val數組代表原數組，f是個二維數組，即上文提到的動態規劃數組，x和y分別對應了圖四-3-1中X區間和Y區間的最小值所在的下標。將這兩部分在原數組中的數值進行比較就能得到整個[a, b]區間內的最小值所在下標了。

ST算法可以擴展到二維，用四維的數組來保存狀態，每個狀態表示的是一個矩形區域中的最值，可以用來求解矩形區域內的最值問題。

五、最近公共祖先相關題集整理

并查集
Is It A Tree? ★☆☆☆☆ 并查集判樹
Farm Irrigation ★☆☆☆☆ 圖的連通性問題
Virtual Friends ★★☆☆☆ 基礎并查集 + 字符串HASH
More is better ★★★☆☆ 基礎并查集
Building Block ★★★☆☆ 并查集（路徑壓縮）
Corporative Network ★★★☆☆ 并查集（路徑壓縮）
Dragon Balls ★★★☆☆ 并查集（路徑壓縮變形）
Connect the Cities ★★★☆☆ 并查集求解最小生成樹
How Many Answers Are Wrong ★★★☆☆ 并查集 擴展
Warfare ★★★☆☆ 并查集 + HASH
Junk-Mail Filter ★★★☆☆ 并查集（擴展操作：刪除）
The k-th Largest Group ★★★★☆ 并查集 + 樹狀數組
Regroup ★★★★☆ 并查集（路徑壓縮）
D-City ★★★★☆ 并查集（離線應用）
Pseudoforest ★★★★☆ 并查集求最大單環森林
Code Lock ★★★★☆ 并查集 + 排列組合
Exclusive-OR ★★★★☆ 并查集 + BFS
RMQ
Balanced Lineup ★☆☆☆☆ 裸RMQ
Frequent values ★★☆☆☆ 區間頻率統計
Sticks Problem ★★☆☆☆ 二分+RMQ
Cartesian Tree ★★★☆☆ RMQ 構造笛卡爾樹
A Famous City ★★★☆☆ RMQ
WorstWeather Ever ★★★★☆ 二分+RMQ
Matrix Searching★★★☆☆ 二維RMQ
Check Corners ★★★☆☆ 二維RMQ
LCA
Nearest Common Ancestors ★☆☆☆☆LCA(小數據)
Closest Common Ancestors ★☆☆☆☆
LCA(小數據)
Distance Queries ★★☆☆☆
LCA求解樹上結點間距離
Connections between cities ★★☆☆☆
LCA求解樹上結點間距離
How far away ★★☆☆☆
LCA求解樹上結點間距離
Tree ★★★☆☆ LCA(RMQ) + 正負tag統計
One and One Story ★★★☆☆ LCA + 并查集
CD Opertaion ★★★☆☆ LCA(RMQ) + 字符串HASH
Parent and son ★★★☆☆ 無根樹LCA
Dylans loves tree ★★★☆☆ LCA + 線段樹
Tri-war ★★★★☆ 三個點的LCA問題
Annoying problem ★★★★☆ LCA
Checkers ★★★★☆ 轉化成二叉樹后二分+ LCA
Traffic Time Query System ★★★★☆ 點雙連通 + LCA
Network ★★★★☆ 邊雙連通 + LCA
An Easy Problem for Elfness ★★★★☆ 主席樹 + LCA
Paths on the tree ★★★★☆ 貪心 + LCA