13

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.

user1580096
  • 487
  • 1
  • 7
  • 17

2 Answers2

8

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:

  1. max_value[v] := maximum continuous sum in v`s subtree
  2. left_value[v] := maximum continuous sum adjacent to the left bound of range corresponding to v's subtree
  3. right_value[v] := maximum continuous sum adjacent to the right bound of range corresponding to v's subtree
  4. 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.

pkacprzak
  • 5,537
  • 1
  • 17
  • 37
  • O(n log(n)) query time does not satisfy the requirement of the question; he wanted a segment tree with O(log n) queries. A query on your segment tree is essentially worse than the O(n) approach. – Justin Oct 24 '13 at 21:08
  • @Justin time per query is O(log(n)), time for O(n log(n)) is a bound for a time needed to insert all n elements in the segment tree – pkacprzak Oct 24 '13 at 21:17
  • could you elaborate on how to calculate the 3 values? when you say maximum continuous sum adjacent to the left bound of range corresponding to v's subtree do you mean the maximum sum in v's left subtree and correspondingly the right subtree for right_value? – otaku Nov 23 '14 at 14:40
  • No, let [a, b] be the range corresponding to `v's` subtree. Then `left_value[v]` is the maximum-sum prefix in this range i.e. a range `[a, i]` where `a <= i <= b` for which the sum is maximal. Does it answer your question? – pkacprzak Nov 23 '14 at 14:46
  • Nope I still don't get it. What would right_value and max_value store then? – otaku Nov 23 '14 at 14:56
  • @AbhyudayaSrinet I gave all 3 definitions – pkacprzak Nov 23 '14 at 15:10
  • ok I understood what values they store but I can't figure out the code that would calculate them and how I would get my answer using the query. – otaku Nov 23 '14 at 15:47
  • It is not enough to store only these three values. There is just not enough data to combine a node from two sub trees. You can refer this value "Maximum/minimum subvector sum" here http://wcipeg.com/wiki/Segment_tree – Alex Lop. Sep 29 '15 at 19:26
  • @AlexLop. Of course it is enough, however, I omitted some details, like storying how far maximum sum adjacent to left/right bound of range is – pkacprzak Sep 29 '15 at 19:31
1

While @pkacprzak's answer describes the solution well, some people might prefer a code example.

#include <iostream>
#define ll long long
using namespace std;
const int N=1<<17; // big power of 2 that fits your data

int n,k;
struct P {ll l, r, ts, bs;}; // left, right, totalsum, bestsum
P p[2*N];

ll maxf(ll a,ll b,ll c) {return max(a,max(b,c));}

P combine(P &cl,P &cr) {
  P node;
  node.ts = cl.ts + cr.ts;
  node.l = maxf(cl.l, cl.ts, cl.ts + cr.l);
  node.r = maxf(cr.r, cr.ts, cr.ts + cl.r);
  node.bs = maxf(cl.bs, cr.bs, cl.r + cr.l);
  return node;
}

void change(int k, ll x) {
  k += N;
  p[k].l = p[k].r = p[k].ts = p[k].bs = x;
  for (k /= 2; k >= 1; k /= 2) {
    p[k] = combine(p[2*k], p[2*k+1]);
  }
}

To add/change values in the segment tree use change(k, x) (O(log(n)) per call) where k is the position and x is the value. The maximum subarray's sum can be read from p[1].bs (top of the tree) after each call to change.

If you also need to find the exact indices of the subarray, you can do a recursive top-down query in O(log(n)) or a binary search of O(log^2(n)) with an iterative query.

EDIT: if we are interested in the maximum subarray of a given subarray, it's best to build a recursive top-down query. See:

https://www.quora.com/How-do-I-calculate-the-maximum-sub-segment-sum-in-a-segment-tree

So to recap, segment trees can handle this problem with changes to the data and with changes to the range we are interested in.

elnygren
  • 5,000
  • 4
  • 20
  • 31