Massive Algorithms: Online LCA

LCA与RMQ互相转化 » NoAlGo博客
http://www.zhihu.com/question/19957473
2. O(n log n) 预处理 + O(1) 查询的在线LCA算法
这个算法不要求事先知道所有查询。来一个查询就处理一个，每处理一个复杂度是常数。其思想是将LCA问题转化成RMQ(Range Minimum/Maximum Query)，然后再利用高效的RMQ算法如线段树，Sparse Table 等求解。对于RMQ问题，如果要追求O(1)的查询复杂度，就不能用线段树了（线段树是O(log n)的），所以可以采用基于动态规划的Sparse Table方法。

(1)将LCA 转化成RMQ:
对于有n个节点的树，我们先建三个一维数组: First[0...n], Depth[0...2*n], Seq[0, 2*n]（稍后解释这三个数组的意义）。然后DFS这棵树，传统的打印DFS序列的流程如下：

function DFS(u)
     u.visit = true
     print u.id
     foreach child v of u
          if v.visit == false
              dfs(v)
          end
     end
end

我们将上述流程修改一下：

function DFS(u)
     u.visit = true
     print u.id
     foreach child v of u
         if v.visit == false
             dfs(v)
         end
         print u.id
     end
end

也就是在每次回溯时我们也把节点u打印一下。可以证明这时的dfs序列长度是2*n-1（传统dfs序列的长度是n

LCA转RMQ主要是通过DFS（深度优先搜索）完成，时间复杂度为O(n)。
DFS时每次进入以及回溯到某一个节点时，我们都记录访问到的节点val，同时记录下这个节点的深度depth。因为进入及回溯时都要记录，所以一个节点可能会被记录多次。另外，为了后面应用RMQ的方便，还使用数组first记录每个元素第一次访问的下标。
http://blog.csdn.net/smallacmer/article/details/7432664
LCA与RMQ问题的转化，LCA问题可以经过DFS+st变成rmq（min）的解法，而且求解的时间复杂度规模是一样的.

DFS时每次进入以及回溯到某一个节点时，我们都记录访问到的节点val，同时记录下这个节点的深度depth。因为进入及回溯时都要记录，所以一个节点可能会被记录多次。另外，为了后面应用RMQ的方便，还使用数组first记录每个元素第一次访问的下标。

例如，下面是一棵以节点0为根节点的多叉树：

以这棵树为例，我们进行DFS时可以得到如下depth数组和val数组：

val	0	1	4	1	5	7	5	1	0	2	0	3	6	3	0
depth	0	1	2	1	2	3	2	1	0	1	0	1	2	1	0

first数组为

下标	0	1	2	3	4	5	6	7
值	0	1	9	11	2	4	12	5

要求x和y的LCA时，因为LCA的深度肯定是最小的，于是可以通过first数组找到x和y首次出现的位置first[x]和first[y]，然后再depth数组查找从first[x]到first[y]的RMQ的下标id，然后在val数组中找到下标id所代表的元素，即为x和y的LCA。

即 LCA(x, y) = val[RMQ(depth, first[x], first[y])]

int depth[mx], val[mx], first[mx];
int id; //记录当前数组的长度
void dfs(int x, int dep)
{
 depth[id] = dep; val[id] = x; first[x] = id; id++;
 for (int i = 0; i < tree[x].size(); i++)
 {
  dfs(tree[x][i], dep+1);
  depth[id] = dep; val[id] = x; id++; //递归完一棵子树回到自身
 }
}

https://gist.github.com/ddrone/2975702
Implementation of online static RMQ-problem with O(N) preprocessing time and O(1) query time Raw

http://kmplayer.iteye.com/blog/604232

struct node //可以添加额外的信息
{
int v;//孩子结点
};
//注意vector在树问题中的使用
vector<node> tree[maxn];
int dfsnum[maxn]; //记录遍历的节点
int depth[maxn]; //记录节点对应的深度
int first[maxn]; //记录结点第一次访问到时的下标
int top; //记录总的步伐数
void dfs(int m,int f,int dep) //当前节点编号,父节点编号,深度
{
dfsnum[top]=m;
depth[top]=dep;
first[m]=top;
top++;
for(unsigned i=0;i<tree[m].size();i++)
{
if(tree[m][i].v==f)
continue;
dfs(tree[m][i].v,m,dep+1);
dfsnum[top]=m; //注:每条边回溯一次,所以top的值=n+n-1
depth[top]=dep;
top++;
}
}
int dp[maxn][18];
void makeRmqIndex(int n,int b[]) //返回最小值对应的下标
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=i;
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
int k=(int)(log((v-s+1)*1.0)/log(2.0));
return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]? dp[s][k]:dp[v-(1<<k)+1][k];
}
int lca(int x,int y)
{
return dfsnum[rmqIndex(first[x],first[y],depth)];
}
int main()
{
int n=5;//顶点数
top=0;
//分别存放每条边的端点
int x[]={1,1,3,3};
int y[]={2,3,4,5};
node temp;
for(int i=0;i<n-1;i++) //n-1条边
{
temp.v=y[i];
tree[x[i]].push_back(temp);
temp.v=x[i];
tree[y[i]].push_back(temp);
}
dfs(1,-1,0); //根节点为1
cout<<"总数:"<<top<<endl;
makeRmqIndex(top,depth);
cout<<"lca(4,5):"<<lca(4,5)<<endl;

http://www.codeproject.com/Articles/141999/Solving-LCA-by-Reducing-to-RMQ-in-C
Read full article from LCA与RMQ互相转化 » NoAlGo博客

Online LCA - Using RMQ

Labels

Popular Posts