LCA 的动态方法

Question

我读了一个 LCA Tutorial 它定义了 P[1,N][1,logN] 其中 P[i][j] 是 i

的第 2j 个祖先

为什么使用 logN 和 为什么使用 2j 祖先？我不明白它的直觉？

我无法理解最后一步：

//we compute LCA(p, q) using the values in P
      for (i = log; i >= 0; i--)
          if (P[p][i] != -1 && P[p][i] != P[q][i])
              p = P[p][i], q = P[q][i];

      return T[p];

Answer 1

如果P[i, j] = 2^j-th ancestor of i，那么：

P[P[i, j - 1], j - 1]

是 i 的 2^(j - 1)-th 祖先的 2^(j - 1)-th 祖先。我们有：

2^(j - 1) + 2^(j - 1) = 2*2^(j - 1) = 2^j

因此，通过像这样定义它，我们实现了一些重要的事情：

内存效率：由于矩阵是n x log n，所以使用的内存是O(n * log n)；
时间效率：因为我们可以通过使用在每一步将问题大致分成 2 的递归来找到每个祖先，所以我们有一个高效的对数每个查询的解决方案。

LCA 的动态方法

Dynamic Approach For LCA

algorithm

tree