最近公共祖先(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 | Sa={(a,e),(d,a)} |
维护并查集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])