最近公共祖先优化

我有包含元素[0至Ñ - 1]一个基本的阵列，其中每个元素是具有索引总是指向前面所述阵列中的位置的结构。最近公共祖先优化

在一个点上，作为一个更大的算法的一部分，我想找到的节点X和之后的任何节点之间的特定ç最低的共同祖先。

int LCA(a, b) { 
    while (a != b) { 
     if (a > b) { 
      a = nodes[a].parent; 
     } else { 
      b = nodes[b].parent; 
     } 
    } 
    return a; 
} 

for (y = x + 1; y < n; ++y) { 
    if (LCA(x, y) == c) { 
     //other code 
    } 
}

上面的代码实际上是伪代码。通过使用生成的查找表，我设法略微提高了LCA（）的性能。事情是这样的：

int LCA(a, b) { 
    if (lookup[a, b]) { 
     return lookup[a, b]; 
    } 
    oa = a; ob = b; 
    while (a != b) { 
     if (a > b) { 
      a = nodes[a].parent; 
     } else { 
      b = nodes[b].parent; 
     } 
    } 
    lookup[oa, ob] = a; 
    lookup[ob, oa] = a; 
    return a; 
}

我知道有可能是一个办法可以让某种专门的LCA（）函数，也就是更换所有上面的代码以某种方式专门它，所以它是相当快。但我没有想到任何有趣的事情。

我已经尝试看看我是否可以简单地通过查看LCA(c, y) == LCA(x, y)做Ç和Y之间的LCA检查，但当然，这是不准确的。

要重新上限：X总是小于Y。 C总是小于X（因此Y）。父母的指数总是比他们的孩子低（因此它是有序的）。

节点知道他们的深度有帮助吗？

此代码占整个算法的CPU时间的80％，总共需要大约4分钟。对此的解决方案可以轻松地改进整个算法。谢谢！

来源

2013-09-25 Mike Weir

属于[codereview.se]或者[cs.se] – millimoose

另外，说实话，我的直觉告诉我，这样做会很好 - 它已经是次线性时间。我很惊讶查找表没有什么帮助，这看起来像是备忘录的主要候选人。有一件事可能会在线性时间以下采用这种方法，那么在您将元素插入此数据结构时将构建查找表，但这可能会带来'O（n^2）'内存开销，使插入速度变慢，而且似乎像这样做不是微不足道的。（假设你用“lookup table”来表示“hashtable”，如果你不这样做，我会用一个）。 – millimoose

记忆不一定有帮助，它取决于你真正得到什么查询。您应该使用更高效的LCA算法。可以通过一些预处理来回答'O（1）'中的查询。 – IVlad

的x和y的LCA会随着x的发生和y在树的euler tour（*）的发生之间的最小高度的节点。要在O(1)时间内找到此项，您需要使用this method来解决RMQ problem。

（*）：您的旅程需要稍作修改才能使用。您每次回到数组时都必须在数组中添加一个值（从递归调用返回给子组）。对于维基树，它应该是这样的：

1 2 3 4 5 6 7 8 9 10 11 
1 2 6 2 4 2 1 3 1 5 1

注意，有没有点有叶子出现两次（虽然它不会影响正确性）。

因此，例如，RMQ(2, 5)将与最小高度的节点出这些：

2 3 4 5 6 7 8 9 10 
2 6 2 4 2 1 3 1 5

哪个节点1。

这不是您可以采取的唯一有效间隔。这也是有效的利用2最后一次出现：

6 7 8 9 10 
2 1 3 1 5

这也将返回1为LCA。

这样，您可以在预处理花费的线性时间在恒定时间内回答LCA查询。

来源

2013-09-25 21:10:53 IVlad

最近公共祖先优化

回答

相关问题