LCA问题的ST,tarjan离线算法解法

一 ST算法与LCA

第一次算法笔记这样的东西，以前学算法只是笔上画画写写，理解了下，刷几道题，其实都没深入理解，以后遇到新的算法要把自己的理解想法写下来，方便日后回顾嘛>=<

RMQ问题就是询问一个给定数组相应区间i…j的最大值。

ST算法的思路是：f（i，j）表示i开始的2^j个数中最大值/最小值，通过运用dp的思想初始化f（i，j）求出每个i（1….n)出发长度为2^j（0<=j<=log(n)/log(2))最大值。

由于初始化过程复杂度只有O（nlog（n))，查询过程O（1），所以会比线段树快很多，而且更不容易出错。

以下为初始化代码：

Init：

for(int i = 1; i <= n; i++)

f(i, 0) = a[i];

for(int i = 1; i <= （int）log(n)/log(2); i++)

for(int j = 1; j + (1<<i) – 1 <= n; j++)

f(i, j) = max(f (i , j-1), f(i+(1<<(j-1) ), j - 1);

查询区间[a, b]，先找到一个最大的值k = (int)log（b-a+1)/log(2);

然后分别查询左右两个端点出发的长度为2^k的区间最大值。

RMQ（a， b）

int k = (int)log(b-a+1)/log(2.0);

return max(f(a, k), f(b – (1<<k) + 1, k));

在dfs遍历过程中，每次进入或回溯到结点u时，将深度存入熟读dep[cnt]，cnt表示在数组中的编号，同时用E[cnt]记录相应的结点即：E[cnt] = u, 并且用R数组记录初次访问u的时候，存进D数组的位置，即R[u] = cnt.

这样每次查询LCA（u，v） = E[RMQ（dep， R[u], R[v])], (R[u] < R[v]),RMQ返回到的是下标R[u]~R[v]的区间中深度最小的点在数组中的位置，也就是下标，这样通过E数组可获得该结点编号。

dfs(u, d)

     R[u] = ++cnt

     dep[cnt] = d

     E[cnt] = u

     vis[u] = true

     for each (u, v) in TREE

           if  !vis[v]

              dfs(v, d+1)

              dep[++cnt] = d

              E[cnt] = u

最后cnt 的大小为2*n-1，也就是每条边访问了2次。

最近遇到的一个问题是，HDU – 3686 Traffic Real Time Query System 对双连通分量缩点，使得割点和各个连通分量构成一个树形图，求这个树形图中任意两点之间路径最少需要经过多少个割点，稍有变化

只是在遇到割点时距离才增加，而且当LCA(u, v)是割点的时候需要把结果ans++。

二 tarjan离线算法解决LCA

主要是事先读入所有的查询，然后在dfs到u的过程中，看所有需要查询的（u，v）中另一点v是否已经访问过，如果是的话此时findset（v）便是u，v的LCA。

通过ans = dis[u] + dis[v] – 2 * dis[findset(v)]便可知道u，v间的最短距离。

常见的LCA问题就是求树形图中2个点的最短距离，3个点连接起来的最短距离，都是通过两两求出最短距离然后除以2（对于3个点的情况），是不是n个点的时候除以（n-1）？猜了一下，求高手证实、==

3个点：题解 ZOJ - 3195 Design the city。2个点的类似： HDU – 2586 How far away ？

更详细的解释博客在这里了，遇到一个LCA的题目，就学习了一下，我只是做了一个新手搬运工hahaha~

、