CODEWITHSUNDEEP
algorithmbinary-tree
Gaurav Arora
Gaurav Arora

Reputation: 183

Maximum Contiguous Sum in O(log n) time

I was reading this blog on Heavy light Decomposition and got confused with this statement:

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.

I know it can be done in O(n) time using Kadane's Algorithm but,

How would you find Maximum Contiguous sum in O(log n) time ?

Upvotes: 2

Views: 680

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

It's possible to adapt Kadane to a segment tree setting, which allows its inclusion in many data structures (see, e.g., my answer here; I should have a proper citation, but it might be folklore).

That being said, the reason that maximum contiguous sum on a path is claimed O(log n) is for the trivial reason that every simple path in a balanced binary tree has length O(log n).

Upvotes: 1

Related Questions