• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			


            

            隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			夜深人靜寫算法（六） - 最近公共祖先
		
            
		
            
		
            目錄  
            一、引例
                  1、樹-結(jié)點間最短距離
            二、LCA（最近公共祖先）
                  1、樸素算法
                  2、步進法
                  3、記憶化步進法
                  4、tarjan算法
                  5、doubly算法
            三、并查集
                   1、"并"和"查"
                   2、樸素算法
                   3、森林實現(xiàn)
                   4、啟發(fā)式合并
                   5、路徑壓縮
                   6、元素刪除
            四、RMQ
                   1、樸素算法
                   2、線段樹（簡介）
                   3、ST算法
            五、最近公共祖先相關(guān)題集整理
            一、引例
                1、樹-結(jié)點間最短距離
                【例題1】給定一棵n(n <= 100000)個結(jié)點的樹，以及m(m <= 100000)條詢問(u, v),對于每條詢問，求u和v的最短距離？
                我們知道，一個普通的無向圖求兩點間最短距離可以采用單源最短路，將時間復雜度大致控制在O(nlogn)，但是當詢問足夠多的時候，這并不是一個高效的算法。從樹的性質(zhì)可知，樹上任意兩點間有且僅有一條簡單路徑（路徑上沒有重點和重邊），所以樹上任意兩點間的最短距離其實就是這條簡單路徑的長度。如圖一-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] - 2*dist[a]。
                那么問題來了，a是什么，我們來看a->r路徑上的所有結(jié)點既是u的祖先，也是v的祖先，所以我們給它們一個定義稱為公共祖先（Common Ancestors），而a作為深度最深的祖先，或者說離u和v最近的，我們稱它為最近公共祖先（Lowest Common Ancestors），簡稱LCA。
             
            圖一-1-1
            二、LCA（最近公共祖先）
                1、樸素算法
                于是求樹上兩點間的距離轉(zhuǎn)化成了求兩個結(jié)點的最近公共祖先問題上來了，最容易想到的辦法是將u->r和v->r的兩條路徑通過遞歸生成出來，并且逆序保存，然后比較兩條路徑的公共前綴路徑，顯然公共前綴路徑的尾結(jié)點就是u和v的最近公共祖先，但是這個算法在樹退化成鏈的時候達到最壞復雜度O(n)，并不可行。
                2、步進法
                對于兩個結(jié)點u和v，假設它們的最近公共祖先為lca(u, v)，用depth[x]表示x這個結(jié)點的深度，pre[x]表示x的父結(jié)點。那么很顯然，有depth[ lca(u, v) ] <= min{depth[u], depth[v]}，通過這樣一個性質(zhì)，我們可以很容易得出一個算法：
                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的網(wǎng)絡拓撲樹，給定兩個客戶端(x, y)，需要找到一個離他們最近的服務器來處理兩個客戶端的交互，客戶端和服務端數(shù)量小于等于1000，但是詢問數(shù)Q <= 10^8。
             
            圖二-3-1
                這是一個典型的LCA問題，并且詢問很多，還有一個特點是總的樹結(jié)點樹并不是很多，所以在步進法計算LCA的時候，可能會遇到很多重復的計算，具體是指計算lca(u, v)的時候可能在某次查詢的時候已經(jīng)被計算過了，那么我們可以把這個二元組預先存在數(shù)組中，即lca[u][v]，這樣做可以避免多次查詢中遇到的冗余計算。但同時也帶來一個問題，就是空間復雜度是O(n^2)，對于n = 100000的情況下內(nèi)存已經(jīng)吃不消了，記憶化步進法只適用于n在千量級的情況。
                4、tarjan算法
                tarjan算法采用深度優(yōu)先搜索遞歸計算結(jié)點(u, v)的LCA。具體的思想是在搜索過程中將一棵樹進行分類，分類如下：
                a.以結(jié)點x為根的子樹作為a類結(jié)點；
                b.以pre[x]為根的子樹去掉a類結(jié)點，為b類結(jié)點；
                c.以pre[ pre[x] ]為根的子樹并且去掉a、b兩類，為c類結(jié)點；依此類推...
             
            圖二-4-1   
                如圖二-4-1所示，對這棵樹進行深度優(yōu)先搜索，深灰色結(jié)點（之所以不用黑色是因為線條也是黑的）表示以該結(jié)點為根的子樹已經(jīng)盡數(shù)訪問完畢；淺灰色結(jié)點表示該結(jié)點為根的子樹正在進行訪問，且尚未訪問完畢；白色結(jié)點表示以該結(jié)點為根的子樹還沒開始訪問。圖中紅色圈出的部分為上文提到的a類結(jié)點；黃色圈出的部分為b類結(jié)點；藍色為c類結(jié)點；綠色為d類結(jié)點，以此類推，不同的顏色屬于不同的集合。所謂一圖在手，勝過萬語千言，從圖中很容易就能看出，x和所有綠色結(jié)點的LCA都為pre[pre[pre[x]]]，即x的曾祖父結(jié)點；和所有藍色結(jié)點的LCA都為pre[pre[x]]，即x的祖父結(jié)點；和所有黃色結(jié)點的LCA都為pre[x]，即x的父結(jié)點。
            可能有人對這里集合的概念表示不理解，舉個例子就能明白了，我們還是沿用上圖，將圖上的結(jié)點進行編號，如圖二-4-2所示，可以得到其中三個集合為：        
                B = {8,13}              C = {4,7,11,12,16}            D = {1,2,3,5,6,9,10,14,15}
                每個集合對應一棵子樹，按照tarjan算法的思路，當給定任意一個結(jié)點，我們需要得到這個結(jié)點所在集合對應的子樹的根結(jié)點，這里分兩步走：
                1) 找到結(jié)點對應的集合；
                2）找到集合的根； 
                第2)步可以預先將值保存在數(shù)組中，但是集合不像數(shù)字，不能作為數(shù)組的下標。而我們注意到這里的集合都是互不相交的，這一點是非常關(guān)鍵的，這就意味著我們可以用一個集合中的元素來作為這個集合的“代表元”。假設B的代表元為13，C的代表元為7，D的代表元為5，用ancestor數(shù)組來存儲集合的根結(jié)點，則有ancestor[13] = 8, ancestor[7] = 4, ancestor[5] = 1，于是第2)步就能在O(1)的時間內(nèi)完成了。
                第1)步其實可以描述成給定一個結(jié)點，求該結(jié)點所在集合的代表元。這里先不討論實現(xiàn)，因為這個操作會在第三節(jié)并查集中花很長的篇幅來講。
             
            圖二-4-2
                對集合有一定了解后，讓我們最后總結(jié)下這個算法究竟是如何實現(xiàn)的。
                1) 初始化所有結(jié)點顏色colors[i] = 0，對樹T進行深度優(yōu)先搜索；
                2) 訪問到結(jié)點u時，將u單獨作為一個集合，并且令ancestor[u] = u，即這個集合的根結(jié)點為u，然后跳轉(zhuǎn)到3)；
                3) 訪問u的所有子結(jié)點v，遞歸執(zhí)行2)，當v所在子樹結(jié)點全部訪問完畢后，將v所在集合和u所在集合合并（執(zhí)行merge(u, v)），并且令新的集合的祖先為u（執(zhí)行ancestor[find(u)] = u）；
                4) 當u所在子樹結(jié)點全部訪問完畢后，置colors[u] = 1，枚舉所有和u有關(guān)的詢問：(u, v)，如果colors[v]等于1，那么記錄u和v的最近公共祖先為ancestor[ find(v) ]；
                這里有兩個神奇的函數(shù)，merge(u, v)和find(u)，其中merge(u, v)表示合并u和v所在的兩個集合，find(u)則表示找到u所在集合的代表元。如果對這個算法已經(jīng)有一定的認知，那么趁熱打鐵，來看下偽代碼是如何實現(xiàn)的。
                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:創(chuàng)建一個集合，集合中只有一個元素u，即{ u }
                注釋2:因為u所在集合只有一個元素，所以也可以寫成ancestor[u] = u
                注釋3:edge[u][0...size-1]存儲的是u的直接子結(jié)點
                注釋4:遞歸計算u的所有直接子結(jié)點v
                注釋5:回溯的時候進行集合合并，將以v為根的子樹和u所在集合進行合并
                注釋6:對合并完的集合設置集合對應子樹的根結(jié)點，find(u)為該集合的代表元
                注釋7:u為根的子樹訪問完畢，設置結(jié)點顏色
                注釋8:枚舉所有和u相關(guān)的詢問(u, v)，如果以v為根的子樹已經(jīng)訪問過，那么ancestor[find(v)]肯定已經(jīng)計算出來，并且必定是u和v的LCA
                tarjan算法的時間復雜度為O(n+q)，其中n為結(jié)點個數(shù)，q為詢問對(u, v)的個數(shù)。但是在進行深搜之前首先需要知道所有的詢問對，所以是一個離線算法，不能實時進行計算，局限性較大。
                【例題3】在一個可視化的界面上的一棵樹，選中某些結(jié)點，然后要求在文件中保存一棵最小的子樹，使得這棵子樹包含所有這些選中的結(jié)點。
                doubly算這個是實際文件保存中比較經(jīng)典的問題，我們可以選擇兩個結(jié)點求出LCA，然后用這個LCA再和兩一個點求LCA，以此類推...n個結(jié)點經(jīng)過n-1次迭代就能求出n個結(jié)點的LCA，這個LCA就是要保存的子樹的根結(jié)點了。
                5、doubly算法
                doubly算法（倍增法）是在線算法，可以實時計算任意兩點間的LCA，并且每次計算時間復雜度是O(1)的。
                該算法同樣也是基于深度優(yōu)先搜索的，遍歷的時候從根結(jié)點開始遍歷，將遍歷的邊保存下來，對于一棵n個結(jié)點的樹來說總共有n-1條邊，那么遍歷的時候需要保存2*(n-1)條邊（自頂向下的邊，以及回溯時的邊，所以總共兩倍的邊），這些邊順序存儲后相鄰兩條邊的首尾結(jié)點必定是一致的，所以可以壓縮到一個一維數(shù)組E中，數(shù)組的長度為2*(n-1)+1，然后建立一個輔助數(shù)組D，長度和E一致，記錄的是E數(shù)組中對應結(jié)點的深度，這個在遍歷的時候可以一并保存，然后再用一個輔助數(shù)組I[i]來保存i這個結(jié)點在E數(shù)組中第一次出現(xiàn)的下標。至此，初始化工作就算完畢了。
                那么當詢問兩個結(jié)點u和v的LCA時，我們首先通過輔助數(shù)組I獲取兩個結(jié)點在D數(shù)組中的位置，即I[u]和I[v]，不妨設I[u] <= I[v],那么在D數(shù)組中的某個深度序列D[ I[u], I[u]+1, ... I[v]-1, I[v] ]，其實表示的是從u到v的路徑上每個結(jié)點的深度，而之前我們已經(jīng)知道樹上任意兩個結(jié)點的簡單路徑有且僅有一條，并且路徑上深度最小的點就是u和v的LCA，所以問題轉(zhuǎn)化成了求D[ I[u], I[u]+1, ... I[v]-1, I[v] ]的最小值，找到最小值所在下標后再到E數(shù)組索引得到結(jié)點的值就是u和v的LCA了。
             
            圖二-5-1
                如圖二-5-1為n = 7個結(jié)點的一棵樹，其中0為根結(jié)點，6條邊分別為(0,5)(5,2)(2,4)(0,3)(3,1)(3,6)。注意這里的邊是有向邊，即一定是父結(jié)點指向子結(jié)點，如果給定的是無向邊，需要預先進行處理。如右圖，從根結(jié)點進行遍歷，其中紅色的邊為自頂向下的邊，綠色的邊為回溯邊，回溯邊一定是子結(jié)點指向父結(jié)點的，藍色的小數(shù)字代表邊的遍歷順序，即第幾條邊，將所有的邊串起來就變成這樣了：
                (0,5) -> (5,2) -> (2,4) -> (4,2) -> (2,5) -> (5,0) -> (0,3) -> (3,1) -> (1,3) -> (3,6) -> (6,3) -> (3,0)
                然后我們將這些邊壓縮到數(shù)組E中，得到：
                E[1 ... 2n-1] = 0 5 2 4 2 5 0 3 1 3 6 3 0
                對數(shù)組E中對應的結(jié)點在樹上的深度記錄在數(shù)組D中，得到：
                D[1 ... 2n-1] = 0 1 2 3 2 1 0 1 2 1 2 1 0
                再將每個結(jié)點在數(shù)組E中第一次出現(xiàn)的位置記錄在數(shù)組I中，得到：
                I[0 ... n-1] = 1 9 3 8 4 2 11
                注意：這里的數(shù)組E和D都是1-based，而I數(shù)組是0-based，這個是個人習慣，可自行約定，不必糾結(jié)。
                根據(jù)LCA的性質(zhì)，有LCA(x, y) = E[ Min_Index( D, I[x], I[y] ) ]，其中Min_Index(Array, i, j)表示Array數(shù)組中[i, j]區(qū)間內(nèi)的最小值對應的下標，那么問題的難點其實就是在于求Min_Index(Array, i, j)了，這個問題就是經(jīng)典的區(qū)間最值問題，最常見的可以采用線段樹求解，建好樹后單次查詢的時間復雜度為O(logn)，當然還有一種更加高效的算法，查詢復雜度可以達到嚴格的O(1)，這就是第四節(jié)要討論的RMQ問題。
                由于tarjan算法中還有一個有關(guān)集合操作的遺留問題尚未介紹，這里先來看史上最輕量級的數(shù)據(jù)結(jié)構(gòu)——并查集。
            三、并查集
                1、"并"和"查"
                并查集是一種處理不相交集合的數(shù)據(jù)結(jié)構(gòu)，它支持兩種操作：
                1）合并操作merge(x, y)。即合并兩個原本不相交的集合，此所謂“并”。
                2）查找操作find(x)。即檢索某一個元素屬于哪個集合，此所謂“查”。
                講個簡單的故事來加深對并查集的理解，這個故事要追溯到北宋年間。話說北宋時期，朝綱敗壞，奸臣當?shù)?，名不聊生。又有外侮遼軍大舉南下，于是眾多能人異士群起而反，各大武林門派同仇敵愾，共抗遼賊，為首的自然是中原武林第一大幫-丐幫，其幫主乃萬軍叢中取上將首級猶如探囊取物、泰山崩于前而面不改色的北喬峰；與其齊名的空有一腔抱負、壯志未酬的南慕容帶領的慕容世家；當然也少不了天下武功的鼻祖-少林，以及一些小幫派，如逍遙派、靈鷲宮、無量劍、神農(nóng)教等等。我們將每個門派（幫派）作為一個集合，從中選出一個代表作為這個集合的標識，姑且認為門派（幫派）的掌門（幫主）就是這個代表。
                作者有幸成了“抗遼聯(lián)盟”的統(tǒng)計員，統(tǒng)計員只有一個工作，就是接收一條條同門數(shù)據(jù)，然后統(tǒng)計共有多少個門派，好進行分派部署。同門數(shù)據(jù)的格式為(x, y)，表示x和y屬于同一個門派，接收到一條數(shù)據(jù)，需要對x所在的群體和y的群體進行合并，當統(tǒng)計完所有數(shù)據(jù)后有多少個集合就代表多少個門派。
                這個問題其實隱含了兩個操作：1、查找a和b是否已經(jīng)在同一個門派；2、如果兩個人的門派不一致，則合并這兩個人所在集合的兩堆人。分別對應了并查集的查找和合并操作。
                如圖三-1-1所示，分別表示丐幫、少林、逍遙、大理段氏四個集合。
             
            圖三-1-1
                2、樸素算法
                接下來來討論下并查集的樸素實現(xiàn)，既然是樸素實現(xiàn)，當然是越樸素越好。樸素的只需要一個數(shù)組就能表示集合，我們用set[i]表示i所在的集合，這樣查找操作的時間復雜度就能通過下標索引達到O(1)（可以把set數(shù)組理解成哈希表）；合并x和y的操作需要判斷set[x]和set[y]是否相等，如果不相等，需要將所有滿足set[i]等于set[x]的set[i]變成set[y]，由于這里需要遍歷set[i]，所以時間復雜度為O(n)。圖三-2-1展示了樸素算法的一個例子，該數(shù)組一共記錄了四個集合，并且用每個集合的最小數(shù)字作為該集合的標識。
             
            圖三-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,每次得到一組數(shù)據(jù)(x, y),就執(zhí)行merge(x, y)，統(tǒng)計完所有數(shù)據(jù)后，對set數(shù)組進行一次線掃，就能統(tǒng)計出總共有多少個門派。
                3、森林實現(xiàn)
                由于樸素實現(xiàn)合并操作的時間復雜度太高，在人數(shù)很多的情況下，效率上非常吃虧，如果有n次合并操作，那么總的時間復雜度就是O(n^2)。所以我們將集合的表示進行一定的優(yōu)化，將一個個集合用樹的形式來組織，多個集合就組成了一個森林。用pre[i]表示i在集合樹上的父結(jié)點，當pre[i]等于i時，則表示i為這棵集合樹的根結(jié)點。那么顯而易見的，對于合并操作(x, y)，只需要查找x和y在各自集合樹的根結(jié)點rx和ry，如果rx和ry不相等，則將rx設為ry的父結(jié)點，即令pre[ry] = rx。查找操作更加簡單，只要順著父結(jié)點一直找到根結(jié)點，就找到了該結(jié)點所在的集合。初始化pre[i] = i，即表示森林中有n棵一個結(jié)點的樹。如圖三-3-1為合并x,y所在集合的操作。
             
            圖三-3-1
                給出森林實現(xiàn)的偽代碼如下：
                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;
                }
                代碼量較樸素算法減少了不少，那時間復雜度呢？仔細觀察，不難發(fā)現(xiàn)兩個操作的時間復雜度其實是一樣的，瓶頸都在查找操作上，來看一個簡單的例子。
                【例題3】因為天下武功出少林，所以很多人都想加入少林習武，令少林寺的編號為1。然后給定m(m <= 100000)組數(shù)據(jù)(x, y)，表示x和y結(jié)成朋友，當x或y等于1時，表示另一個不等于1的人帶領他的朋友一起加入少林，已知總?cè)藬?shù)n，求最后少林寺來了多少人。
                一個最基礎的并查集操作，對于每條數(shù)據(jù)執(zhí)行merge(x, y)即可，最后一次線性掃描統(tǒng)計1所在集合的人數(shù)的個數(shù)，但是對于極限情況，還是會退化成O(n)的查找，如圖三-3-2所示，每次合并都是一條鏈合并到一個結(jié)點上，使得原本的樹退化成了鏈，合并本身是O(1)的，但是在合并前的查找根結(jié)點的過程中已經(jīng)是O(n)的了，為了避免集合成鏈的情況，需要進行啟發(fā)式合并。
             
            圖三-3-2
                4、啟發(fā)式合并
                啟發(fā)式合并是為了解決合并過程中樹退化成鏈的情況，用depth[i]表示根為i的樹的最大深度，合并ra和rb時，采用最大深度小的向最大深度大的進行合并，如果兩棵樹的最大深度一樣，則隨便選擇一個作為根，并且將根的最大深度depth自增1，這樣做的好處是在n次操作后，任何一棵集合樹的最大深度都不會超過log(n)，所以使得查找的復雜度降為O( log(n) ）。
                給出啟發(fā)式合并的偽代碼如下：
                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;
                        }
                    }
                }
                啟發(fā)式合并的查找操作不變，合并操作引入了depth數(shù)組，并且在合并過程中即時更新。
                5、路徑壓縮
                【例題4】n(n <= 100000)個門派編號為1-n，經(jīng)過m(m <= 100000)次江湖上的血雨腥風，不斷產(chǎn)生門派吞并，每次吞并可以表示成(x, y)，即x吞并了y，最后問從前往后數(shù)還存在的編號第k大的那個門派的編號。
                啟發(fā)式合并通過改善合并操作提高了效率，但是這個問題的合并是有向的，即一定是y向x合并，所以無法采用按深度的啟發(fā)式合并，那么是否有辦法優(yōu)化查找操作來改善效率呢？答案是一定的，我們可以在結(jié)點x找到樹根rx的時候，將x到rx路徑上的點的父結(jié)點都設置為rx，這樣做并不會改變原有的集合關(guān)系，如圖三-5-1所示。
             
            圖三-5-1
                由于每次查找過程中都對路徑進行了壓縮，使得任何時候樹的深度都是小于4的，從而查找操作可以認為是常數(shù)時間。
                當然，如果合并是無向的同樣可以采用路徑壓縮，這樣做會導致樹的深度可能時刻在變化，所以啟發(fā)式合并的啟發(fā)值不能采用樹的深度，可以通過一個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;
                        }
                    }
                }
                仔細觀察不難發(fā)現(xiàn)，路徑壓縮版本的find和merge操作與啟發(fā)式合并的版本除了紅色標注部分，其它完全相同（只是merge函數(shù)中depth變量名換成了rank），find函數(shù)中的賦值操作（紅色部分代碼）很好地詮釋了深度優(yōu)先搜索在回溯時的完美表現(xiàn)，find函數(shù)的返回值一定是這棵集合樹的根結(jié)點root，回溯的時候會經(jīng)過從x到root的路徑，通過這一步賦值可以很輕松的將該路徑上所有結(jié)點的父結(jié)點都設為根結(jié)點root。
                6、元素刪除
                【例題5】話說有人加入少林，當然也有人還俗，虛竹就是個很好的例子，還俗后加入了逍遙派，這就是所謂的集合元素的刪除。
                并查集的刪除操作可以描述成：在某個集合中，將某個元素孤立出來成為一個只有它本身的新的集合。這步操作不能破壞原有的樹結(jié)構(gòu)，單純“拆”樹是不現(xiàn)實的，如圖三-6-1所示,是我們的美好預期，但是事實上并做不到，因為在并查集的數(shù)據(jù)結(jié)構(gòu)中只記錄了x的父親，而未記錄x的子結(jié)點，沒辦法改變x子結(jié)點的父結(jié)點。
             
            圖三-6-1
                而且就算是記錄了子結(jié)點，每次刪除操作最壞情況會更新n個子結(jié)點的父結(jié)點，使得刪除操作的復雜度退化成O(n)，還有一個問題就是x本身如果就是根結(jié)點，那么一旦x刪除，它的子結(jié)點就會妻離子散，家破人亡，需要重新建立關(guān)系，越想越復雜。
                所以，及時制止記錄子結(jié)點的想法，采用一種新的思維——二次哈希法（ReHash），對于每個結(jié)點都有一個哈希值，在進行查找之前需要將x轉(zhuǎn)化成它的哈希值HASH[x]，那么在進行刪除的時候，只要將x的哈希值進行改變，變成一個從來沒有出現(xiàn)過的值（可以采用一個計數(shù)器來實現(xiàn)這一步），然后對新的值建立集合，因為只有它一個元素，所以必定是一個新的集合。這樣做可以保證每次刪除操作的時間復雜度都是O(1)的，而且不會破壞原有樹結(jié)構(gòu)，唯一的一個缺點就是每刪除一個結(jié)點其實是多申請了一塊內(nèi)存，如果刪除操作無限制，那么內(nèi)存會無限增長。
            四、RMQ
                1、樸素算法
                RMQ (Range Minimum/Maximum Query)問題是指：對于長度為n的數(shù)列Array，回答若干詢問RMQ(Array,i,j)(i,j<=n)，返回數(shù)列Array中下標在i,j里的最小(大）值（或者最?。ù螅┲邓诘南聵耍簿褪钦f，RMQ問題是指求區(qū)間最值的問題。
                樸素算法就是枚舉區(qū)間的值進行大小判定，如果長度為n的數(shù)組，詢問個數(shù)為q，那么算法的時間復雜度為O(qn)。
                2、線段樹（簡介）
                線段樹是一種二叉搜索樹，它的每個結(jié)點都保存一個區(qū)間[l, r]，如果當l等r時，表示該結(jié)點是一個葉子結(jié)點；否則它必定有兩個子結(jié)點，兩個子結(jié)點保存的區(qū)間分別為[l, mid]和[mid+1, r],其中mid = (l+r)/2的下整，利用二分（分治）的思想將一個長度為n的區(qū)間分割成一系列單位區(qū)間（葉子區(qū)間）。
                線段樹的每個結(jié)點都可以保存一些信息，最經(jīng)典的應用就是區(qū)間最值，可以在結(jié)點上保存該結(jié)點對應區(qū)間[l, r]上的最值，每次詢問[A, B]區(qū)間最值時將區(qū)間[A, B]進行劃分，劃分成一些區(qū)間的并集，并且集合中的區(qū)間必定都能在線段樹結(jié)點上一一對應，可以證明一定存在這樣一個劃分，并且劃分的集合個數(shù)不會超過logn，從而使得每次查詢的時間復雜度能夠保證在O(logn)。
                由于線段樹還有很多經(jīng)典應用，不想在這篇文章快要結(jié)束的時候草草了事，所以在標題上加了“簡介”二字，等到日后有時間再詳細介紹吧。
                3、ST算法
                ST（Sparse Table）算法是基于動態(tài)規(guī)劃的，
            用f[i][j]表示區(qū)間起點為j長度為2^i的區(qū)間內(nèi)的最小值所在下標，通俗的說，就是區(qū)間[j, j + 2^i)的區(qū)間內(nèi)的最小值的下標。
                從定義可知，這種表示法的區(qū)間長度一定是2的冪，所以除了單位區(qū)間(長度為1的區(qū)間)以外，任意一個區(qū)間都能夠分成兩份，并且同樣可以用這種表示法進行表示，
            [j, j + 2^i)的區(qū)間可以分成
            [j, j+2^(i-1))和[j + 2^i)，于是
            可以列出狀態(tài)轉(zhuǎn)移方程為： f[i][j] = RMQ( f[i-1][j], f[i-1][j+2^(i-1)] )。
                f[m][n]的狀態(tài)數(shù)目為n*m = nlogn，每次狀態(tài)轉(zhuǎn)移耗時O(1)，所以預處理總時間為O(nlogn)。
                原數(shù)組長度為n，當[j, j + 2^i)區(qū)間右端點 j + 2^i - 1 > n時如何處理？在狀態(tài)轉(zhuǎn)移方程中只有一個地方會下標越界，所以當越界的時候狀態(tài)轉(zhuǎn)移只有一個方向，即當j + 2^(i-1) > n 時，f[i][j] = f[i-1][j]。
                求解f[i][j]的代碼就不給出了，只需要兩層循環(huán)的狀態(tài)轉(zhuǎn)移就搞定了。
                f[i][j]的計算只是做了一步預處理，但是我們在詢問的時候，不能保證每個詢問區(qū)間長度都是2的冪，如何利用預處理出來的值計算任何長度區(qū)間的值就是我們接下來要解決的問題。
                首先只考慮區(qū)間長度大于1的情況（區(qū)間長度為1的情況最小值就等于它本身），給定任意區(qū)間[a, b] (1 <= a < b <= n)，必定可以找到兩個區(qū)間X和Y，它們的并是[a, b]，并且區(qū)間X的左端點是a，區(qū)間Y的右端點是b，而且兩個區(qū)間長度相當，且都是2的冪，如圖所示：
             
            圖四-3-1
                設區(qū)間長度為2^k，則X表示的區(qū)間為[a, a + 2^k)，Y表示的區(qū)間為(b - 2^k, b]，則需要滿足一個條件就是X的右端點必須大于等于Y的左端點減一，即 a+2^k-1 >= b-2^k，則2^(k+1) >= (b-a+1), 兩邊取對數(shù)（以2為底），得 k+1 >= lg(b-a+1)，則k >= lg(b-a+1) - 1，k只要需要取最小的滿足條件的整數(shù)即可( lg(x)代表以2為底x的對數(shù) )。
                仔細觀察發(fā)現(xiàn)b-a+1正好為區(qū)間[a, b]的長度len，所以只要區(qū)間長度一定，k就能在常數(shù)時間內(nèi)求出來。而區(qū)間長度只有n種情況，所以k可以通過預處理進行預存。
                當lg(len)為整數(shù)時，k 取 lg(len)-1，否則k為 lg(len)-1 的上整（并且只有當len為2的冪時，lg(len)才為整數(shù)）。
                代碼如下：
                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數(shù)組代表原數(shù)組，f是個二維數(shù)組，即上文提到的動態(tài)規(guī)劃數(shù)組，x和y分別對應了圖四-3-1中X區(qū)間和Y區(qū)間的最小值所在的下標。將這兩部分在原數(shù)組中的數(shù)值進行比較就能得到整個[a, b]區(qū)間內(nèi)的最小值所在下標了。
                ST算法可以擴展到二維，用四維的數(shù)組來保存狀態(tài)，每個狀態(tài)表示的是一個矩形區(qū)域中的最值，可以用來求解矩形區(qū)域內(nèi)的最值問題。
            五、最近公共祖先相關(guān)題集整理
                并查集
            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       ★★★★☆     并查集 + 樹狀數(shù)組
            Regroup                      ★★★★☆     并查集（路徑壓縮）
            D-City                       ★★★★☆     并查集（離線應用）
            Pseudoforest                 ★★★★☆     并查集求最大單環(huán)森林
            Code Lock                    ★★★★☆     并查集 + 排列組合
            Exclusive-OR                 ★★★★☆     并查集 + BFS
                RMQ
            Balanced Lineup              ★☆☆☆☆    裸RMQ
            Frequent values              ★★☆☆☆    區(qū)間頻率統(tǒng)計
            Sticks Problem               ★★☆☆☆    二分+RMQ
            Cartesian Tree               ★★★☆☆    RMQ 構(gòu)造笛卡爾樹
            A Famous City                ★★★☆☆    RMQ
            WorstWeather Ever            ★★★★☆    二分+RMQ
            Matrix Searching             ★★★☆☆    二維RMQ
            Check Corners                ★★★☆☆    二維RMQ
                LCA
            Nearest Common Ancestors     ★☆☆☆☆
                
            LCA(小數(shù)據(jù)) 
            Closest Common Ancestors     ★☆☆☆☆    
            LCA(小數(shù)據(jù))
            Distance Queries             
            ★★☆☆☆    
            LCA求解樹上結(jié)點間距離
            Connections between cities   ★★☆☆☆
                LCA求解樹上結(jié)點間距離
            How far away                 ★★☆☆☆
                LCA求解樹上結(jié)點間距離
            Tree                         ★★★☆☆    LCA(RMQ) + 正負tag統(tǒng)計
            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                     ★★★★☆    轉(zhuǎn)化成二叉樹后二分+ LCA
            Traffic Time Query System    ★★★★☆    點雙連通 + LCA
            Network                      ★★★★☆    邊雙連通 + LCA
            An Easy Problem for Elfness  ★★★★☆    主席樹 + LCA
            Paths on the tree            ★★★★☆    貪心 + LCA
            
		
            
		
            
			posted on 2015-12-10 00:14 英雄哪里出來 閱讀(29768) 評論(3)  編輯 收藏 引用  所屬分類: 算法專輯 
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				
            
					# re: 夜深人靜寫算法（六） - 最近公共祖先  回復  更多評論
					  
				
            
				dist[u] + dist[v] - dist[a]

            這里不應該減兩個dist[a]嗎？
				
            
					2015-12-22 16:45 | 張晴川
				
            
			
            
		
			
            
				
            
					# re: 夜深人靜寫算法（六） - 最近公共祖先  回復  更多評論
					  
				
            
				@張晴川
            哈哈是的，筆誤了，多謝指正~~
				
            
					2015-12-26 14:11 | 英雄哪里出來
				
            
			
            
		
			
            
				
            
					# re: 夜深人靜寫算法（六） - 最近公共祖先  回復  更多評論
					  
				
            
				丐幫、少林、逍遙、大理段氏四個集合

            有意思
				
            
					2016-01-06 15:41 | bns
				
            
			
            
		

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



午夜欧美精品久久久久久久|
久久只有这精品99|
九九久久自然熟的香蕉图片|
99久久99久久精品免费看蜜桃|
久久精品99久久香蕉国产色戒|
久久成人影院精品777|
久久久精品国产Sm最大网站|
久久亚洲高清综合|
伊人色综合久久天天人手人婷|
久久狠狠高潮亚洲精品|
久久国产福利免费|
色欲久久久天天天综合网精品|
国产精品18久久久久久vr|
久久er国产精品免费观看8|
久久久久久久久久久精品尤物|
久久久精品免费国产四虎|
精品久久综合1区2区3区激情|
久久人人爽人人爽人人片av麻烦|
久久精品国产亚洲av日韩|
久久99精品久久久久久噜噜|
精品国产乱码久久久久软件
|
久久精品免费观看|
亚洲国产成人精品女人久久久
|
国产精品免费久久久久久久久|
久久香综合精品久久伊人|
亚洲精品高清久久|
久久精品aⅴ无码中文字字幕不卡|
亚洲国产精品热久久|
亚洲色欲久久久综合网|
久久久久噜噜噜亚洲熟女综合|
久久99国产乱子伦精品免费|
综合久久给合久久狠狠狠97色|
久久成人国产精品二三区|
亚洲国产美女精品久久久久∴|
久久精品无码av|
久久综合丝袜日本网|
久久久久久九九99精品|
久久亚洲国产成人影院|
久久99精品国产麻豆不卡|
久久夜色精品国产亚洲|
久久久久久久久久久久中文字幕|