My submission for the MARBLESGF prob(Dec13 Long) was based on the idea that I store the initial sum a[o] to a[i] in s[i], and then keep a track of all the changes made, so that whenever sum is asked for I need to just add these changes to it.
The foll sol( aum9W7 - Online C Compiler & Debugging Tool - Ideone.com ) got accepted in which I keep track of the changes in an array, which takes O(Q) time in worst case to compute the sum and hence O(Q^2) for the whole prog.
While in the sol( nQpx7n - Online C Compiler & Debugging Tool - Ideone.com ) where I got TLE, I kept track of the changes using a Red-Black tree so that in worst case to compute the the sum it would be of O(R+log Q), where R would be the no of elem that have been changed, within the range of elem whose sum is to be calculated.
Np. I think that you get TLE on test cases that have a high number of changes and low range querys, so R+logQ>query range. Strange… I would expect the contrary… the first solution to fail on O(Q^2).
I would suggest binary indexed trees or segment trees for optimal time.
I was the setter for this problem, and, as described by @jackal02, the main algorithmic idea I had in mind while setting this problem was to use Fenwick Trees/Segment Trees, as I didn’t know about this structure, so I used this problem to also learn about it, and in my solution I use Fenwick Trees
I can’t access the link you have provided for your TLE solution, so, I can’t check it against my test files, to see where exactly it is that you have TLE, but, for sure there are test cases where almost only changes are made and a single sum computation is required, so, those sort of cases along with possibly some additional complexity in building a Red-Black Tree might result in TLE versus your other approach, as Q = 50000 and Q^2 = 2500000000, for the entire program, I think that with some sort of precomputations maybe you could still get AC, or, maybe I don’t have files where only maximum sums are required to be computed and then maybe you can get AC with such approach…
hey, I hadn’t made it clear in the decription: R is the no of elem that have been changed(in the range) which is <Q , so the second code looks directly into the elem(s) which have been changed using search for start and end points,while the first one checks for all of 'em.
And thank you for suggesting binary indexed tree.
