Schieber Vishkin Algorithm O(n)-O(1) lca
缪凌锴_Mathew
·
·
算法·理论
Schieber Vishkin algorithm 基于状压、位运算 O(n)-O(1) 在线求解 LCA。
讲得不是很清楚的汉化版
核心思想是满二叉树上的快速 LCA。
省流：神秘二进制树剖，快速求 x 子树内包含 y 的儿子。
记号：lb(i) 表示 i 的二进制最低位，hb(i) 表示 i 的二进制最高位，二进制位从 0 开始编号。
以下“x 的祖先”包含 x。
满二叉树快速 LCA
观察满二叉树的中序遍历：
观察 x 与 x 的父亲 F_x 二进制的关系。比如 11\to 10\to 12\to 8。
\begin{aligned}
11&=101\red1\\
10&=10\red10\\
12&=1\red100\\
8&=\red1000\\
\end{aligned}
注意到 lb(F_x)=lb(x)+1，lb(x) 是 x 到叶子的距离。记 x 的高度为其到叶子的距离（lb(x)）。
- 第 $lb(x)$ 位变为 $0$。
- 第 $lb(x)+1$ 位必定是 $1$。
人话：从叶子开始，二进制最右端有一个 $1$，每跳一次父亲，$1$ 往左挪一位，原来的位置变为 $0$。
$\gdef\lca{\operatorname{lca}}
求解 \lca(x,y)：
\begin{aligned}
x&=A\red0?\\
y&=A\red1?\\
\end{aligned}
其中 A 是 x,y 二进制的 \mathrm{lcp}，标红的位是 hb(x\oplus y)。
若 x 的 ? 部分全是 0，\lca(x,y)=x，特判这种情况。
于是 $\lca(x,y)$ 可以 $O(1)$ 求出。
再观察中序遍历，**结论：$\lca(l,l+1,\dots,r)$ 是 $[l,r]$ 内 $lb$ 最大的数**。这个数显然可以唯一确定。
---
### 神秘二进制树剖
记 $d_i$ 为 $i$ 的 dfs 入栈序（先序遍历），$f_i$ 为 $i$ 子树内 $lb(d_j)$ 的最大的 $d_j$。
$i$ 子树内的 $d$ 值显然是连续的，故 $f_i$ 唯一。
一棵可能的树：
$d$ 树（之后的图都是用 $d$ 重标号过的）：
$x$ 的实儿子是 $f$ 与 $x$ 相等的儿子，以此树剖。
**结论：若 $x$ 在原树上是 $y$ 的祖先，则 $f_x$ 在满二叉树上是 $f_y$ 的祖先。**
显然 $lb(f_x)\ge lb(f_y)$，若 $f_x=f_y$ 显然满足，考虑证明 $f_x\ne f_y$（$lb(f_x)>lb(f_y)$）：
$$
\begin{aligned}
f_x&=A\red100\dots000\dots0\\
f_y&=B???\dots\red100\dots0\\
\end{aligned}
$$
标红的位置是 $f_x,f_y$ 的 $lb$。
$d$ 值在 $f_x,f_y$ 之间的点都在 $x$ 的子树内，且 $f_x$ 是其中 $lb$ 最大的。
- $A<B$，$B\red000\dots\red000\dots000$ 比 $f_x$ 的 $lb$ 值更大，矛盾。
- $A>B$，$A\red000\dots\red000\dots000$ 比 $f_x$ 的 $lb$ 值更大，矛盾。
故 $A=B$。
所以 $f_y$ 可以根据满二叉树的跳父亲过程把 $1$ 挪到 $lb(f_x)$ 上，得证。
在满二叉树上 $x$ 的祖先只有 $O(\log n)$ 个，所以每个点到根的路径上至多 $O(\log n)$ 条虚边。
~~也就是说也可以当正常树剖用，只是每条实链不一定到叶子。~~
---
### 快速 LCA
原树求 $\lca(x,y)$，不妨设为 $z$，考虑找到满二叉树上 $f_x,f_y$ 的公共祖先 $p$。
但是 $f_z$ 不一定等于 $p$，就比如上面图例中 $\lca(3,7)=1$，但是 $p=4$，$f_1=8$。
根据结论，可以知道 $f_z$ **在满二叉树上**是 $p$ 的祖先。
考虑记录 $S_x$ 表示 $x$ **在原树上**的祖先的 $f$ 值**在满二叉树上**的高度集合。状压存储。
即 $S_x=\{lb(f_i)|i\in anc(x)\}$，$anc(x)$ 为 $x$ **在原树上**的祖先集合。
$lb(f_z)\in S_x$，$lb(f_z)\in S_y$ 且 $lb(f_z)\ge lb(p)$（在满二叉树上比 $p$ 高）。
显然可以通过一系列位运算求出 $f_z$。
那么问题来了，如何由 $f_z$ 倒推回 $z$？
一条实链的 $f$ 值相同，现在知道 $z$ 在哪条实链上。
只需要知道 $x,y$ 到这条实链上的最近点 $x',y'$，$x',y'$ 中深度更小的即为 $z$。
考虑怎么求 $x'$，$y'$ 同理。
$f_x=f_z$ 显然 $x'=x$，只考虑 $f_x\ne f_z$ 的情况。
考虑求出 $x'$ 往 $x$ 方向的儿子（子树内包含 $x$ 的儿子）$m$。$m$ 是其所在实链的链顶。
$lb(f_z)$ 和 $lb(f_m)$ 都在 $S_x$ 内，且在 $S_x$ 内 $f_z$ 前驱为 $f_m$，故 $f_m$ 也可以位运算求出。
又 $m$ 是 $f$ 值为 $f_m$ 的链顶，故可以推出 $m$，进而知道 $x'$。
终于，$O(1)$ 求出了 $\lca(x,y)$！
而且求 $m$ 的做法可以 $O(1)$ 求“$x$ 往 $y$ 方向的儿子”。
---
### 实现
[评测记录](https://www.luogu.com.cn/record/227266542)
```cpp
basic_string <int> tr[MAXN];
inline void add_edge(int x,int y){
tr[x].push_back(y);
}
int lb[MAXS],hb[MAXS];
int dfc=0;
int fat[MAXN],top[MAXN],d[MAXN],f[MAXN],s[MAXN];
inline void dfs1(int x){
dfc++;
d[x]=dfc;
f[x]=dfc;
for(int to:tr[x])
{
if(to==fat[x]){
continue;
}
fat[to]=x;
dfs1(to);
if(lb[f[to]]>lb[f[x]]){
f[x]=f[to];
}
}
top[f[x]]=x;
}
inline void dfs2(int x){
s[x]|=1<<lb[f[x]];
for(int to:tr[x])
{
if(to^fat[x]){
s[to]=s[x];
dfs2(to);
}
}
}
inline int lca(int x,int y){
if(f[x]==f[y]){
return d[x]<d[y]?x:y;
}
int p=hb[f[x]^f[y]];
int h=lb[(s[x]&s[y])>>p<<p];
int F=(f[x]>>h|1)<<h;
if(f[x]^F){
int m=hb[s[x]&((1<<h)-1)];
m=(f[x]>>m|1)<<m;
x=fat[top[m]];
}
if(f[y]^F){
int m=hb[s[y]&((1<<h)-1)];
m=(f[y]>>m|1)<<m;
y=fat[top[m]];
}
return d[x]<d[y]?x:y;
}
```
[树剖板子评测记录](https://www.luogu.com.cn/record/227279240)