c++ - 最低的共同祖先优化

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

一方面，作为更大算法的一部分，我想在节点X和之后的任何节点之间找到特定的C最低公共(public)祖先。

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)来简单地在C和Y之间进行LCA检查，但这当然是不准确的。

概括一下:X总是小于Y。C总是小于X(因此也就是Y)。 parent 总是比 child 的索引低(因此是有序的)。

知道节点深度的节点对您有帮助吗？

此代码占整个算法的CPU时间的80％，总共花费约4分钟。解决此问题的方法将很容易改进整个算法。谢谢!

最佳答案

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

(*):您的游览需要稍作修改才能生效。每次返回数组时(从递归调用返回给 child )，都必须在数组上附加一个值。对于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查询。

lca

c++ - 最低的共同祖先优化