随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

夜深人静写算法（六） - 最近公共祖先

目录  
一、引例
      1、树-结点间最短距离
二、LCA（最近公共祖先）
      1、朴素算法
      2、步进法
      3、记忆化步进法
      4、tarjan算法
      5、doubly算法
三、并查集
       1、"并"和"查"
       2、朴素算法
       3、森林实现
       4、启发式合并
       5、路径压缩
       6、元素删除
四、RMQ
       1、朴素算法
       2、线段树（简介）
       3、ST算法
五、最近公共祖先相关题集整理
一、引例
    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] - 2*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

posted on 2015-12-10 00:14 英雄哪里出来 阅读(29346) 评论(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理