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.
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?
Oh..Okay,I think I get it now.. Thankyou for the explanation,It was very clear..
max(-1000000, val) to avoid summing big negative numbers, which may lead to overflow.
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,
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..
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 -∞ .
well, that is very problem specific. And also it will be a bad advice leading to people thinking that you can simply use max(-1000000, val) which will get WA otherwise. That's why I pointed out. Also why not use long long int instead, which is much safer.
This problem was an example, there are a lot of problems which you may end up with summing negative infinity and even using long long won't help to avoid the overflow, or using the long long may get you TLE, so you will need to this maximizing. And yes, in this problem there is no need to maximizing (looks like the code author recycled this code from another solution), i answered the question in general, my bad i didn't make it clear.
mind giving an actual example? I haven't come across any so far.
Sure, no problem: http://codeforces.net/contest/527/problem/C http://codeforces.net/contest/722/problem/C https://csacademy.com/contest/archive/task/array-removal/
Thanks, though for the first problem. You don't need to use that, also I dont see how you use that. same goes for the second and the third. Sorry, but I was asking for such example where long long won't help to avoid the overflow, or using the long long may get you TLE. Also, mind showing me the solution that uses that?
Any problem could be solved by many approaches, what's new? http://codeforces.net/contest/527/submission/27432319 http://codeforces.net/contest/722/submission/21087744 The third one is the same concept.
ok, i got it from your solution. Thanks.