I wanted to find the largest sum continuous subarray from the given array. I know the O(n) approach of finding the largest sum continuous subarray approach using the concept of dynamic programming using Kadane's algorithm.
But it will take a lot of time if the no of range queries are very large. Is there a way to solve it using Segment-Trees as it is the best option preferred to answer range queries which it solves in O(log(n)) time. Thank you.
According to my comment to Justin's answer, you can augment a standard segment tree to achieve a O(log(n)) query time with O(n log(n)) time to build the tree i.e. to insert all n elements into the tree.
The idea is to store in every node v not just one value, but four:
- max_value[v] := maximum continuous sum in v`s subtree
- left_value[v] := maximum continuous sum adjacent to the left bound of range corresponding to v's subtree
- right_value[v] := maximum continuous sum adjacent to the right bound of range corresponding to v's subtree
- sum[v] := the sum of all elements in v's subtree
In order to perform an update operation for a node v, you have to recompute max_value[v], left_value[v], right_value[v], sum[v]. This is very straightforward and I think you can figure it out by yourself - there are a few cases to consider.
A query operation is similar to a query operation in a basic segment tree. The only difference is that in this case, you have to consider also the left_value[v] and the right_value[v] while computing a result - again, there are a few easy cases to consider.
I hope that you'll figure out omitted details. If not, let me know and I'll give a more detailed explanation.