树上倍增法

一 点睛

树上倍增法不仅可以解决 LCA问题，还可以解决很多其他问题。

F[i，j] 表示 i 2^j 辈祖先，即 i 节点向根节点走 2^j 步到达的节点。

u 节点向上走 2^0步，即为 u 的父节点 x， F[u,0] = x ；向上走 2^1 步到达 y，F[u,1] = y;向上走 2^2 步到达z,F(u,2) = z;向上走 2^3 步,节点不存在，令 F[u,3] =0。

F[i,j] 表示 i 的 2^j 辈祖先，即 i 节点向根节点走 2^j 步到达的节点。可以分成两个步骤：i 节点先向根节点走 2^(j-1) 步得到 F[i,j-1],再从 F[i,j-1] 节点出发向根节点走 2^(j-1) 步得到 F[F[i,j-1],j-1],该节点为F[i,j]。

递推公式 F[i,j]=F[F[i,j-1],j-1]。

二 算法设计

1 创建 ST，

2 利用 ST 求解 LCA。

三 图解

和暴力搜索中的同步前进方法一样，先让深度大的节点 y 向上走到与 x 同一深度，然后 x、y 一起向上走。和暴力搜索不同的是，向上走是按照倍增思想走，不是一步步向上走的，因此速度比较快。

1 怎样让深度大的节点 y 向上走到与 x 同一深度？

假设 y 的深度比 x 深度大，需要 y 向上走到与 x 同一深度，k=3，则求解过程如下。

a  y 向走 2^3 步,到达的节点的深度比 x 深度小，什么也不做。

b 减少增量，y 向上走 2^2 步，此时到达节点深度比 x 深度大，y 向上移，y=F[y][2]。

c 减少增量，y 向上走 2^1 步，此时到达节点深度与 x 深度相等。y 上移，y=F[y][1]。

d 减少增量，y 向上走 2^0 步，到达的节点深度比 x 深度小，什么也不做。此时 x，y 在同一深度。

总结，按照增量递减的方式，到达的节点深度比 x 深度小时，什么也不做；到达的节点深度大于或等于 x 深度时，y上移，直到增量为 0，此时，x、y 在同一深度。

2 x、y 一起向上走，怎么找到最近公共祖先？

假设 x、y 已到达同一深度，现在一起向上走，k=3，则其求解过程如下。

a x、y 同时向上走 2^3 步,到达的节点相同，什么也不做.

b 减少增量，x、y 同时向上走 2^2 步，此时到达节点不同，x、y 上移，x=F[x][2],y=F[y][2]。

c 减少增量，x、y 同时向上走 2^1 步，此时到达节点不同，x、y 上移，x=F[x][1],y=F[y][1]。

d 减少增量，x、y 同时向上走 2^0 步，此时到达节点相同，什么也不做。

此时 x、y 的父节点为最近公共祖先节点，即 LCA(x,y)=F[x][0]。

完整图解如下。

总结：按照增量递减的方式，到达的节点相同时，什么也不做；达到的节点不同时，同时上移，直到增量为 0。此时 x、y 的父节点为公共祖先节点。