动态方法对于LCA [英] Dynamic Approach For LCA

问题描述

我读一LCA 教程如果它定义P [1，N] [1，logN个]，其中P [i] [j]为i的2J个祖先

为什么是 logN个使用和为什么2J祖先使用？我不知道这是直觉？

我不明白的最后一步：

  //我们计算LCA（P，Q）使用P中的价值
      对于（i =记录; I＆GT; = 0;我 - ）
          如果（P [P] [I] = -1＆安培;！＆安培; P！[P] [I] = P [Q] [I]）
              P = [P] [I]中，Q = P [Q] [I];

      返回T [P];
 

解决方案

如果 P [I，J] = 2 ^ j个的我的祖先，则：

  P [P [I，J  -  1，J  -  1]
 

是 2 ^（j - 1）个的祖先2 ^（j - 1）个祖先我。我们有：

  2 ^（j  -  1）+ 2 ^（j  -  1）= 2 * 2 ^（j  -  1）= 2 ^Ĵ
 

因此​​，通过定义它像我们实现了几个重要的事情：

1. 内存效率：由于矩阵是 NX为log N ，使用的内存为为O（n * log n）的;

2. 时间效率：因为我们可以通过使用一个循环，大约分裂问题2在每一步中找到彼此的祖先，我们对每个查询的效率，对数解

I reading a LCA Tutorial Where it defines P[1,N][1,logN] where P[i][j] is the 2j-th ancestor of i

Why it is using logN and why 2j ancestor is used ? I did not understand it's intuition ?

I could not understand the last step :

//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];

解决方案

If P[i, j] = 2^j-th ancestor of i, then:

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

Is the 2^(j - 1)-th ancestor of the 2^(j - 1)-th ancestor of i. We have:

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

So by defining it like that we achieve a couple of important things:

1. Memory efficiency: since the matrix is n x log n, the memory used is O(n * log n);

2. Time efficiency: because we can find each ancestor by using a recurrence that splits the problem roughly in 2 at each step, we have an efficient, logarithmic solution for each query.

这篇关于动态方法对于LCA的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！