Hi,

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.