algorithm - O(log n) 时间内的最大连续总和

Question

我正在阅读 this关于 Heavy light Decomposition 的博客，并对以下声明感到困惑:

If a balanced binary tree with N nodes is given, then many queries can be done with O( log N ) complexity. Distance of a path, Maximum/Minimum in a path, Maximum contiguous sum etc etc.

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

如何在 O(log n) 时间内找到最大连续总和？

Answer 1

可以使 Kadane 适应线段树设置，这允许它包含在许多数据结构中(参见，例如 my answer here ；我应该有一个适当的引用，但这可能是民间传说)。

也就是说，路径上的最大连续和被声明为 O(log n) 的原因是平衡二叉树中每条简单路径的长度为 O(log n) 的微不足道的原因。