问O(log n)时间的最大连续和
EN

Stack Overflow用户

提问于 2016-01-24 08:55:06

回答 1查看 527关注 0票数 2

我当时正在阅读这关于重轻分解的博客，我对这句话感到困惑：

如果给出一个具有N个节点的平衡二叉树，则可以使用O( log )复杂度进行多个查询。路径的距离，路径中的最大/最小，最大连续和等。

我知道用Kadane算法可以在O(n)时间内完成，但是，

如何在O(log )时间内求最大连续和?

algorithm

发布于 2016-01-24 14:00:39

可以将Kadane调整为段树设置，这允许将其包含到许多数据结构中(例如，请参阅我在这里的回答；我应该有一个适当的引用，但可能是民俗)。

尽管如此，声称路径上的最大连续和是O(log )的原因是因为平衡二叉树中的每条简单路径都有长度O(log n)。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/34973856

复制

相似问题

问O(log n)时间的最大连续和EN