Content #
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], i=1,2,...,n, j=0,1,2,...,k, 2^k<=n, k=log2(n)
算法实现 #
void st_create() {
for (int j = 1; j <= k; j++)
for (int i = 1; i <= n; i++)
F[i][j] = F[F[i][j - 1]][j - 1]
}
int lca_st_query(int x, int y) {
if (d(x) > d(y)) { //保证x的深度小于或等于y的深度
swap(x, y);
}
for (int i = k; i >= 0; i--)
if (d(F[y][i]) >= d(x))
y = F[y][i];
if (x == y)
return x;
for (int i = k; i >= 0; i--)
if (F[x][i] != F[y][i])
x = F[x][i], y = F[y][i];
return F[x][0];
}
From #
《算法训练营进阶篇》 陈小玉