最近公共祖先(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])