转自:
http://www.cppblog.com/Icyflame/
一、定义与定理
LCA:Least Common Ancestors(最近公共祖先),对于一棵有根树T的任意两个节点u,v,求出LCA(T, u, v),即离跟最远的节点x,使得x同时是u和v的祖先。
在线算法:用比较长的时间做预处理,但是等信息充足以后每次回答询问只需要用比较少的时间。
离线算法:先把所有的询问读入,然后一起把所有询问回答完成。
RMQ:给出一个数组A,回答询问RMQ(A, i, j),即A[i...j]之间的最值的下标。
二、DFS+RMQ
1)Sparse Table(ST)算法
描述:
1 //初始化
2 INIT_RMQ
3 //max[i][j]中存的是重j开始的i个数据中的最大值,最小值类似,num中存有数组的值
4 for i : 1 to n
5 max[0][i] = num[i]
6 for i : 1 to log(n)/log(2)
7 for j : 1 to n
8 max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
9 //查询
10 RMQ(i, j)
11 k = log(j-i+1) / log(2)
12 return MAX(max[k][i], max[k][j-2^k+1])
分析:初始化过程实际上是一个动态规划的思想。易知,初始化过程效率是O(nlogn),而查询过程效率是O(1)。ST是一个在线算法。
示例:POJ 3368 解题报告
2)求解LCA问题
描述:
(1)DFS:从树T的根开始,进行深度优先遍历,并记录下每次到达的顶点。第一个的结点是root(T),每经过一条边都记录它的端点。由于每条边恰好经过2次,因此一共记录了2n-1个结点,用E[1, ... , 2n-1]来表示。
(2)计算R:用R[i]表示E数组中第一个值为i的元素下标,即如果R[u] < R[v]时,DFS访问的顺序是E[R[u], R[u]+1, ..., R[v]]。虽然其中包含u的后代,但深度最小的还是u与v的公共祖先。
(3)RMQ:当R[u] ≥ R[v]时,LCA[T, u, v] = RMQ(L, R[v], R[u]);否则LCA[T, u, v] = RMQ(L, R[u], R[v]),计算RMQ。
由于RMQ中使用的ST算法是在线算法,所以这个算法也是在线算法。
示例:ZOJ 3195 解题报告。
三、Tarjan算法
描述:Tarjan算法是一个离线算法,也就是说只有先获得所有的查询,再按一个特定的顺序进行运算。
1 //parent为并查集,FIND为并查集的查找操作
2 Tarjan(u)
3 visit[u] = true
4 for each (u, v) in QUERY
5 if visit[v]
6 ans(u, v) = FIND(v)
7 for each (u, v) in TREE
8 if !visit[v]
9 Tarjan(v)
10 parent[v] = u
示例:HDOJ 2586 解题报告。