algorithm - 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] = i 的第 2^j 个祖先，则:

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

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

1. 内存效率:由于矩阵是n x log n，所以使用的内存是O(n * log n)；

2. 时间效率:因为我们可以通过使用在每一步将问题大致分成 2 的递归来找到每个祖先，所以我们对每个查询都有一个高效的对数解决方案。 p>