LCA问题，在一棵有根数中找两个节点u,v的最近公共祖先.有多种算法实现，我这里简要总结一下它的基于跳表的倍增实现和与RMQ的关系.
跳表倍增实现
对于朴素的算法是把每个节点的深度和父亲预处理出来，然后先把两个节点的高度对齐，然后在对每一个节点后退，直到到达公共父亲为止.可以发现这样的算法是 O(n) 的. 我们可以预处理出每一个节点的 2k 个祖先.这样每次就可以后退 2k 步. 很显然在让两个节点高度对齐的时候我们也只需沿着他们的高度差的二进制对齐.(具体详见代码). 在高度后退的时候我们可以沿着2k个祖先走，不过由于anc[u][k]==anc[v][k] 的时候anc[u][k] 一定是 u,v 的公共祖先，(祖先的祖先当然是祖先).为了防止退过头了,即跳过最近公共祖先，我们只在 anc[u][k]!=anc[v][k] 的时候后退.
code
std::vector<int> G[MAX_V];//基于倍增的跳表实现struct LCA{ const int LOG_V = 30; int V; int root;//树根 int anc[MAX_V][LOG_V];//每一个节点的(2^k)个祖先 int depth[MAX_V]; //找节点的深度和父亲. void dfs(int v,int p,int d){ anc[v][0] = p; depth[v] = d; for(int i=0 ; i<G[v].size() ; ++i) if(G[v][i]!=p)dfs(G[v][i],v,d++)//这是树，边的关系只有父亲节点和子孙. } //预处理，倍增 void init(){ dfs(root,-1,0); for(int k = 0 ; k<LOG_V ; ++k){//过剩处理不影响结果. for(int i = 0 ; i<V ; ++i) if(anc[i][k] == -1)anc[i][k+1] = -1; else anc[i][k+1] = anc[anc[i][k]][k];//2^(k+1)为2^k祖先的2^k祖先. } } int lca(int u,int v){ //跑到同一高度. if(depth[u]<depth[v])swap(u,v); for(int k=0 ; k<LOG_V ; ++k) if((depth[u]-depth[v])>>k & 1)//差的二进制走 u = anc[u][k]; if(u==v)return u; for(int k= LOG_V-1 ; k>=0 ; k--) if(anc[u][k]!=anc[v][k]){//避免跳过最近祖先 u = anc[u][k]; v = anc[v][k]; } return anc[u][0]; }};RMQ与LCA的关系.
我们知道RMQ问题是可以做到 (O(nlgn)−O(lgn))(前面是预处理时间后面表示在线查询时间).我们将LCA问题归约到RMQ问题.
RMQ向LCA问题的转化
对于一个长度为N的序列来说我们可以按照如下方法将其建为一棵优先级树. 1. 找到其对应的最小值 Ak 作为根节点. 2. 将 [A1,...,Ak−1] 作为其左子树，将 [Ak+1,...,AN]作为其右子树. 3. 递归的建立它的左子树和右子树.
显然复杂度是O(nlgn)
RMQ归约LCA
对于 RMQ(A,i,j) 1. i≤k≤j那么答案为Ak,Ak正好为i,j的LCA. 2. k<i,那么答案为RMQ([Ak+1,...,AN],i,j). 3. k>j,那么答案为RMQ([A1,...,Ak−1],i,j).
因此 RMQ(i,j)⇒LCA(i,j)!，即RMQ可以归约到LCA
LCA向RMQ的转化
对于有根数T的遍历我们定义如下序列.
欧拉序列 F: 对有根树T进行 dfs 得到的节点序列2N−1个(与度数有关).深度序列 D: 遍历到的序列的深度.pos(u) 值 : 在 dfs 中第一次出现 u的位置.如图 
由 dfs 的性质, 从 u 到 v 仅经过一次 LCA(u,v),深度最小因此 LCA(u,v)=RMQ(D,pos(u),pos(v))
int rmq_dp[MAX_V*2][64];//返回下标的RMQ；void RMQ_init(const int *A,int n){ for(int i=0 ; i<n ; ++i)rmq_dp[i][0] = i; for(int j = 1 ; (1<<j)<=n ; ++j) for(int i =0 ; i+(1<<j)-1<n ; ++i) if(A[rmq_dp[i][j-1]]<A[rmq_dp[i+(1<<(j-1))][j-1]]) rmq_dp[i][j] = rmq_dp[i][j-1]; else rmq_dp[i][j] = rmq_dp[i+(1<<(j-1))][j-1];}//最小值的下标int query(const int *A,int L,int R){ int k=0; while((1<<(k+1))<=R-L+1)k++; if(A[rmq_dp[L][k]]<A[rmq_dp[R-(1<<k)+1][k]]) return rmq_dp[L][k]; else return rmq_dp[R-(1<<k)+1][k];}//LCAstd::vector<int> G[MAX_V];struct LCA{ int root; int vs[MAX_V*2];//访问数组 int depth[MAX_V*2];//深度数组 int pos[MAX_V];//位置数组 void dfs(int v,int p,int d,int& k){ pos[v] = k; vs[k] = v; depth[k++] = d; for(int i=0 ; i<G[v].size() ; ++i) if(G[v][i] !=p){ dfs(G[v][i],v,d+1,k); vs[k] = v;//回退 depth[k++] = d; } } //预处理 void init(int V,int r = 1){ root = r; int k=0 ; dfs(root,-1,0,k); RMQ_init(depth,2*V-1); } int lca(int u,int v){ if(pos[u]>pos[v])swap(u,v); return vs[query(depth,pos[u],pos[v])]; }};模板题 poj 1130这题有毒，同样的代码，RE一次，CE一次，然后才让过.
