最近公共祖先(Lowest Common Ancestor)的定义：同一棵树的节点u，v，定义:

lca(u,v)为分别包含u、v的全部该树的子树的并集中的最小高度树的根节点。

下面介绍四种求最近公共祖先的方法。暴力法、倍增法、Tarjan算法，RMQ算法。

暴力法

标记现在的点访问过；向上跳到父节点。

重复这一过程，直到跳到的父节点被标记为访问过。

时间复杂度O(n)(还需要O(n)清除标记)。

一种不需要清除标记的优化方法：将访问标记和查询次数对应：第i次查询标记i，这样就可以不需要清除标记。

DP标记——倍增算法

标记一组f[i][j]，标记i节点的上方第$2^j$个节点。

深的节点向上跳，跳到相同的高度。

可以利用DP标记向上跳：比如说深度相差7，分别跳4，2，1。

同时向上跳：同时跳到最深的不同节点，直到跳到父节点相同为止。

时间复杂度：O_{init}(nlgn),O_{query}(lgn), 空间复杂度：O(nlgn)

这是一个在线算法。

Tarjan算法

将所有的查询lca(a,e),lca(c,e),lca(d,a)建立查询集合

1
2
3
4
5
6
7

Sa={(a,e),(d,a)}

Sc={(c,e)}

Sd={(d,a)}

Se={(a,e),(c,e)}

维护并查集UFS(u)->u

一遍DFS，完成所有查询。

进入节点u：对于查询集合Su中的每一个查询lca(u,v)：

• 如果查询没有访问过，标记被访问。

• 如果查询被访问过，lca(u,v)=UFS(v)

Union(UFS(v),UFS(father_v))->UFS(v)

这是一个离线算法。

此处的UFS为并查集：定义操作：查找find(u)，并union(u,v):u<=>v。

时间复杂度：O_{init}(n+m),O_{query}(n+m(lgn)), 空间复杂度：O(n)

RMQ 区间最值查询算法

区间最小值查询（Range Minimum Query）的定义：对于数组list，

rmq(l,r) = min_{l<=k<r} list[k]

RMQ: Sparse Table算法

建立数组st[i][j]为区间[i,i+2^j)的区间最小值下标。

（可以递推：st[i] [j] = min{st[i][j-1],st[i+2^{j-1}][j-1]}建立）

询问：设t为r-l+1的二进制最高位数，则有

rmq(l,r) = min{st[l][t], st[r-2^t+1][t]}

因为上面的集合一定覆盖[l,r]。

用RMQ解决LCA

先DFS一棵树，记录DFS顺序表为seq。

DFS顺序：DFS搜索所经过的所有节点，包括已经经过的重复节点。（长度2n-1（参考电路理论的树））

用first[node]记录节点node在第一次出现的位置。

此时lca(u,v)=seq.rmq(first[u],first[v])