4

我有一个包含元素 [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() 函数，也就是说，以某种方式替换所有上述代码以对其进行专门化，这样它会快得多。但我没有想到任何有趣的事情。

我试图通过查看 if 来查看是否可以简单地在 C 和 Y 之间进行 LCA 检查，但这当然不LCA(c, y) == LCA(x, y)准确。

重申一下：X总是小于Y。C总是小于X（因此Y）。父母的指数总是低于他们的孩子（所以它是有序的）。

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

这段代码占了整个算法 CPU 时间的 80%，总共需要大约 4 分钟。对此的解决方案将很容易从整体上改进算法。谢谢！

4

1 回答 1

4

的LCA和将是在你的树的欧拉环(*) 中的出现x和出现y之间具有最小高度的节点。要及时找到这个，需要用这种方法解决RMQ问题。xyO(1)

(*)：您的游览需要稍作修改才能正常工作。每次返回数组时（从对子的递归调用中返回），您也必须在数组中附加一个值。对于 wiki 树，它看起来像这样：

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-25T21:10:53.030 回答