Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Quick question: | Reply
Just to see if I get it:
For the problem given, a.k.a summing over a given range, this is not a good solution, since we can do O(1) if we simply use partial sums in a temp array (sum(i,j) = partialSum(j) - partialSum(i)).
Nevertheless, this structure is good when asking different questions about a range (e.g. maximum value in a given range / RMQ ).
My point is - the given example (taken from topCoder) should have been chosen differently.

Am I wrong ?
Subject Author Date
Quick question: assaf.sela Sep 21, 2012 at 4:59 PM EDT
Re: Quick question: hex539 Sep 21, 2012 at 6:06 PM EDT