我有一个包含元素 [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分钟。对此的解决方案很容易改进整个算法。谢谢!
最佳答案
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
查询,而花费在预处理上的时间是线性的。
关于c++ - 最低公共(public)祖先优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19015012/