final_tsu's blog

Help needed in Maximum Range Sum (segment tree) problem.
By final_tsu, history, 7 years ago, In English

Hi :) I am new to competitive programming and was trying to figure out how segment trees work. I covered the basics of segment tree like the Range minimum query which was pretty trivial. I then,started another problem that bowled me over..SPOJ GSS1 Problem Statement After trying for some time,I saw the solution...Solution

First of all,I am a newbie at the moment so I request all the pros to explain me how would someone in layman terms think of taking 4 values (sum,pref,suf,ans) in a tree node instead of just one.. Okay,this one might have been obvious to some experienced players,but my next doubt is the in the function "combine"..In the 5th line..

((res.ans = max (max (l.ans, r.ans), l.suff + r.pref);))

we are setting ans for the new tree node,by combining the left and right child node.. I am not able to Digest the above mentioned line...can someone prove me that the above mentioned line is actually correct and will work in all the cases..it doesnt looks like it's going to work for every case(but it is)..I tried to prove it myself but I can't.... Lastly on line 64..

((res.pref = res.suff = res.ans = max(-1000000, val);))

we are setting maxprefix sum as maximum btween -1000000 and val...why don't we set it to val directly?!

Thank you for being patient and helping a newcomer.

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

Comments Comments (13)
| Write comment?
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

For second question, from what I can tell, you should be able to set to val directly. I might be wrong, but I think you are right.

The idea is to pretend that you have already solved for the first and second half of the array. How can you store information about the first and second halves such that you can combine them to get the answer for the whole array?

Now you can think, well, if I solved for first and second half already, I don't have to consider any range sums which are entirely in the first half, or entirely in the second half (i.e. doesn't cross halfway). These are already handled.

Now, you can realise that all you need to consider are range sums which cross the halfway point. How do you calculate this? You take maximum suffix of first half, maximum suffix of second half, and this is the best range sum over the halfway point. Now you only have three options for your answer: the old answers for first and second half, and the new one you calculated. This is correct because we covered all cases.

To think of similar solutions from now on, just think: how do I solve for the whole array with information about first and second half?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Oh..Okay,I think I get it now.. Thankyou for the explanation,It was very clear..

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

max(-1000000, val) to avoid summing big negative numbers, which may lead to overflow.

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

    Thankyou,that seems like it,but if max(-1000000,val) returns -1000000 then won't the answer come out to be wrong? either way we get a WA..I am confused,

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

      I submitted without the max, and I still got AC. this is because val is always larger than -1000000, so it will always return val. I have no idea why did they use max..

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

        I agree with you, the maximizing has no benefit here at all, but i was talking generally.. maximizing between -∞ (-1000000) and a number is to avoid overflow.

        I remember a problem in which you given an array of numbers and two types of queries, one to get the maximum sum in a range, and the other to destroy some index, the destroyed index can't be included in any range sum, you can simply handle this by setting -∞ to the destroyed index, but you may get overflow after merging, so you should make sure that the nodes values doesn't exceed -∞ .

        → Reply