倍增 Binary Lifting

O(n log n) 预处理祖先表 fa[u][k]，O(log n) 查询 LCA。观察二进制分解跳跃与两节点同步上跳过程。

速度:

蓝色=u 及其路径，紫色=v 及其路径，绿色=已跳过的节点，黄色=LCA 结果

祖先表 fa[u][k]（u 的 2^k 级祖先，-1 表示不存在）:

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1

树上 10 个节点，预处理倍增祖先表 fa[u][k] = u 的 2^k 级祖先

步骤 1 / 17初始化

当前高亮行: 1(初始化)

1const LOG = 4; // 2^3=8 足够覆盖树深

2const fa = Array.from({ length: n }, () => new Array(LOG).fill(-1));

3for (let u = 0; u < n; u++) fa[u][0] = parent[u];

4for (let k = 1; k < LOG; k++)

5 for (let u = 0; u < n; u++)

6 fa[u][k] = fa[u][k-1] < 0 ? -1 : fa[fa[u][k-1]][k-1];

7function lca(u, v) {

8 if (depth[u] < depth[v]) [u, v] = [v, u];

9 for (let k = 0, d = depth[u]-depth[v]; d > 0; k++, d >>= 1)

10 if (d & 1) u = fa[u][k]; // 二进制分解跳祖先

11 if (u === v) return u;

12 for (let k = LOG-1; k >= 0; k--)

13 if (fa[u][k] !== fa[v][k]) { u = fa[u][k]; v = fa[v][k]; }

14 return fa[u][0];

15}

加载中…

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1

u \ k	2^0	2^1	2^2	2^3
0	-1	-1	-1	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1
4	-1	-1	-1	-1
5	-1	-1	-1	-1
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1