使用欧拉序 st 表 O(1) 求 LCA

欧拉序 st 表求 LCA

一开始是从某篇题解里看到的，后来百度了一下就会了（

这是一种预处理 O(nlogn) ，查询 O(1) 的优秀算法。

什么是欧拉序

举个例子，下面是一棵树：

上面有 dfs 与回溯的过程。

将整个 dfs 与回溯过程写出来：

1  →  2  →  4  →  7  →  4  →  8  →  4  →  2  →  5  →  2  →  1  →  3  →  6  →  3  →  1 

这就是欧拉序了。

如何求出答案

如何求 LCA 呢？

假设我们要求 LCA(3,7) 。

那我们先把欧拉序中 3,7 第一次出现的位置 标出来。

1  →  2  →  4  →  7  →  4  →  8  →  4  →  2  →  5  →  2  →  1  →  3  →  6  →  3  →  1 

LCA(3,7) 就是欧拉序标红的 3,73,7 之间深度最小的点，就是 11 。

暴力找一遍 3,73,7 之间深度最小的点肯定不行。

由于欧拉序不变，此时可以用 \text{st}st 表的方法优化，就能 O(1)O(1) 查询。

设 f[i][j] 表示欧拉序中第 ii 个点以及后面共 2^j 个点中深度最小的点。

dfs 预处理出欧拉序：

#define N 1000007
int n,m,rt;
struct edge{
    int to,nxt;
}e[N<<1];
int tot,head[N];
inline void adde(int u,int v){
    e[++tot]=(edge){v,head[u]};
    head[u]=tot;
}

int dep[N],lg[N<<1],f[N<<1][21];
int dfn[N<<1],que[N<<1],idx;
void dfs(int u,int pa)
{
    dfn[u]=++idx,que[idx]=u;
    dep[u]=dep[pa]+1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pa)continue;
        dfs(v,u);
        que[++idx]=u;
    }
}

建 st 表：

void buildst()
{
    For(i,1,idx)f[i][0]=que[i];
    For(j,1,20)
        for(int i=1;i+(1<<j)<=idx;++i){
            int f1=f[i][j-1],f2=f[i+(1<<j-1)][j-1];
            f[i][j]=dep[f1]<dep[f2]?f1:f2;
        }
    lg[0]=-1;
    For(i,1,idx)lg[i]=lg[i>>1]+1;
}

查询：

inline int getlca(int u,int v)
{
    if(dfn[u]>dfn[v])swap(u,v);
    u=dfn[u],v=dfn[v];
    int kk=lg[v-u+1],f1=f[u][kk],f2=f[v-(1<<kk)+1][kk];
    return dep[f1]<dep[f2]?f1:f2;
}

看了一下 P3379 提交记录，发现 O(logn) 的树剖跑的比这个 O(1) 还快

update :

在 某题 里把树剖 LCA 换成了 st 表求 LCA 结果快了不少。

看来 st 表求 LCA 可以在查询次数多的情况下 用来卡常。