最近公共祖先优化

Question

我有一个基础数组，包含[0到N-1]个元素，每个元素都是一个结构体，其中索引始终指向数组中较早的位置。

在一个更大的算法中的某个时刻，我想要找到节点X和之后任何节点之间的特定C个最低公共祖先。

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()函数，即以某种方式替换上述所有代码，使其专门化，从而使其速度更快。但我还没有想到任何有趣的解决方案。

我尝试过检查C和Y之间是否存在LCA检查，即检查LCA(c, y) == LCA(x, y)，但当然这是不准确的。

简要概括一下： X始终小于Y。 C始终小于X（因此也小于Y）。父节点始终在比它们的子节点更低的索引处（因此有序）。

节点知道它们的深度是否有帮助呢？

此代码占整个算法80%的CPU时间，总共需要大约4分钟。解决此问题将轻松改善整个算法。谢谢！

- Mike Weir

---

适合发布在[codereview.se]或者[cs.se]上。 - millimoose

而且，说实话，我的直觉告诉我这已经是最好的结果了 - 它已经是次线性时间了。我很惊讶查找表并没有帮助太多，这似乎是备忘录化的一个主要候选项。唯一可以使这个算法达到线性以下时间复杂度的方法是在插入元素到数据结构中时同时建立查找表，但这可能会带来O(n^2)的内存开销，使插入变得更慢，并且似乎不是一件容易的事情。（假设你所说的“查找表”是指“哈希表”。如果不是，我会使用哈希表。） - millimoose

备忘录技术并不一定有帮助，这取决于你实际得到的查询。你应该使用更高效的LCA算法。通过一些预处理，可以在O(1)时间内回答查询。 - IVlad

有关预处理的建议吗？我没有使用哈希表 - 而是使用了一个二维数组。 - Mike Weir

你能解释一下你的查找表如何帮助吗？ - ArjunShankar

更新了我的答案，关于查找表。 - Mike Weir

Answer 1

x和y的最低公共祖先是指在树的欧拉遍历中，x和y首次出现的位置之间高度最小的节点。要在O(1)时间内找到它，您需要使用RMQ问题的解决方案来解决，使用这种方法。

（*）：为使其有效，请对此进行微小修改。每当返回时（从对子项的递归调用返回），您必须向数组附加一个值。对于维基树，它看起来像这样：

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查询。

- IVlad