RMQ求LCA【ST】算法

RMQ求LCA其实非常简单的啦

我们需要理解两个基本的工具：

1.欧拉序列；

2.线段树，二叉搜索树或者其它基本区间寻求最值的方法；

所以说LCA和区间有什么关系？

举个栗子：

RMQ求LCA【ST】算法

我们将欧拉序列E打出：

【1,2,4,2,5,2,1,3,6,3,1】（先自己想想怎么实现）

在打印序列的同时记录下每个节点第一次出现的位置R

【1,2,8,3,5,9】

另外别忘了给欧拉序列标深度L

【1,2,3,2,3,2,1,2,3,2,1】

接下来区间最值的作用就发挥了作用了：

比如我们要找4和5LCA，我们只需要在R数组中找到【3，5】中深度最小的节点就行了；

而对应的区间可以通过R数组来确定；

接下来是moban（蒟蒻只能用领接链表建）：

首先是欧拉序列的打印：

 
void dfs(int u,int dep)
{ tot++;
   R[u]=tot;//这里是第一次出现的位置；
   L[tot]=dep;
   E[tot]=u;
   vis[u]=true;
for(int i=head[u];i!=0;i=nex[i])
{int v=to[i];
    if(!vis[v]){    
    dis[v]=dis[u]+w[i];
    dfs(v,dep+1);
    E[++tot]=u;//别忘了回到u节点记录；
    L[tot]=dep;}
}
}

接下来是ST对序列进行处理（我们记录的不是最小深度，而是最小深度对应的节点）

不明白ST的可以看我的另一篇博客：https://blog.****.net/Wyt_code/article/details/83832104

void found()//STmoban不多说；
{ for(int i=1;i<=tot;i++)
    f[i][0]=i;
  int n=(int)(log(tot)/log(2));
   for(int j=1;j<=n;j++)
       for(int i=1;i<=tot;i++)
           if(i+(1<<j)-1<=tot){
               int a=f[i][j-1];int b=f[i+(1<<j-1)][j-1];
               if(L[a]<L[b]) f[i][j]=a;//注意是记录下标以便确定节点；
                 else f[i][j]=b;
                 }
             }

接下来是RMQ和LCA的查询（为了便于理解我分成两个板块）

int RMQ(int l,int r)
{int j=(int)(log(r-l+1)/log(2));
int a=f[l][j];int b=f[r-(1<<j)+1][j];
return L[a]<L[b]?a:b;//还是返回数组对应下标；
}
 
int LCA(int l,int r)
{ l=R[l];r=R[r];//确定区间；
    if(l>r) swap(l,r);
    return E[RMQ(l,r)];//读求下标对应节点；
}

emmmm好像就这些了

RMQ求LCA【ST】算法

相关推荐