rb9's blog

By rb9, 4 years ago, In English,

I was trying to solve this problem http://www.spoj.com/problems/GSS1/, after sometime I gave up and googled approach for it, I found this website https://kartikkukreja.wordpress.com/2014/11/09/a-simple-approach-to-segment-trees/ but still not able to understand problem and its solution.Plz help!

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I will explain my approach and I will give you my code.

In this problem we need to keep a structure in each node that can help us to determine the answer for a node from its children. The structure that I used is the following:

struct Node
{
    int sum_left,sum_right,sum_max,sum_total;
    bool indicator;
};

sum_left — the maximum sum of consecutive elements that contains the leftmost element in the range.

sum_right — the maximum sum of consecutive elements that contains the rightmost element in the range.

sum_max — the answer for the interval.

sum_total — the total sum of the elements in the range.

indicator — flag that tells us whether sum_max=sum_total. That is, the whole interval is the one with maximum sum.

Obviously, for leaf nodes indicator=true and sum_right=sum_left=sum_max=sum_total=[The current element in the array].

For non-leaf nodes:

sum_left=(left child).sum_left

if (left child).indicator=true, then sum_left+=(right child).sum_left

sum_right=(right child).sum_right

if (right child).indicator=true, then sum_right+=(left child).sum_right

sum_total=(left child).sum_total + (right child).sum_total

sum_max=max((left node).sum_max,(right node).sum_max,sum_left,sum_right,sum_total,(left node).sum_right+(right node).sum_left)

My code is here.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply! Can you explain what is meant by this " Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } "

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It means the maximum sum of consecutive elements from the interval [x;y].

      For example, let's take the array 1,2,3,-100,5.

      Query(1;5) = 6 (1+2+3).

      Query(3;5) = 5 (5).

      Query(4;4) = -100 (-100).

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Now, completely understood,question statement and reason why we apply segment tree not kadane algo. Thanks for your help :D!