c++ - 最低公共(public)祖先优化

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() 函数，也就是说，以某种方式替换上面的所有代码以使其专门化，从而使其速度相当快。但是我没有想到任何有趣的事情。

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

回顾一下:X 总是小于 Y。 C 总是小于 X(因此 Y)。 parent 的指数总是低于他们的 child (因此是有序的)。

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

这段代码占整个算法CPU时间的80%，总共耗时约4分钟。对此的解决方案很容易改进整个算法。谢谢!

Answer 1

x 和 y 的 LCA 将是 x 和 y 出现之间高度最小的节点在 euler tour 中出现 y (*) 你的树。要在 O(1) 时间内找到它，您需要解决 RMQ problem使用 this method .

(*):您的导览需要稍作修改才能正常工作。每次返回数组时(从对子项的递归调用返回)，您也必须向数组附加一个值。对于 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 查询，而花费在预处理上的时间是线性的。