糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

[转]LCA问题(含RMQ的ST算法)

转自: 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 解题报告

posted on 2010-03-10 14:14 糯米 阅读(1261) 评论(1)  编辑 收藏 引用 所属分类: Algorithm

评论

# re: [转]LCA问题(含RMQ的ST算法)   回复  更多评论   

重j开始的i个数据中的最大值
应该是 从j开始的2^i个数据中的最大值
2010-07-18 10:03 | xx

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理