使用欧拉序 st 表 O(1) 求 LCA
Rainbow_qwq
·
·
个人记录
欧拉序 \text{st} 表求 LCA
一开始是从某篇题解里看到的，后来百度了一下就会了（
这是一种预处理 O(n\log n) ，查询 O(1) 的优秀算法。
什么是欧拉序
举个例子，下面是一棵树：
上面有 \text{dfs} 与回溯的过程。
将整个 \text{dfs} 与回溯过程写出来：
1\to 2\to 4\to 7\to 4\to 8\to 4\to 2\to 5\to 2\to 1\to 3\to 6\to 3\to 1
这就是欧拉序了。
如何求出答案
如何求 \text{LCA} 呢？
假设我们要求 \text{LCA(3,7)} 。
那我们先把欧拉序中 3,7 第一次出现的位置 标出来。
1\to 2\to 4\to \color{red}7 \color{blue} \to 4\to 8\to 4\to 2\to 5\to 2\to 1\to \color{red}3 \color{black}\to 6\to 3\to 1
暴力找一遍 $3,7$ 之间深度最小的点肯定不行。
由于欧拉序不变，此时可以用 $\text{st}$ 表的方法优化，就能 $O(1)$ 查询。
设 $f[i][j]$ 表示欧拉序中第 $i$ 个点以及后面共 $2^j$ 个点中深度最小的点。
$\text{dfs}$ 预处理出欧拉序：
```cpp
#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;
}
}
```
建 $\text{st}$ 表：
```cpp
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;
}
```
查询：
```cpp
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(\log n)$ 的树剖跑的比这个 $O(1)$ 还快~~
update :
在 某题 里把树剖 LCA 换成了 $\text{st}$ 表求 LCA 结果快了不少。
看来 $\text{st}$ 表求 LCA 可以在查询次数多的情况下 ~~用来卡常~~。