CareerCup

I'm assuming you have O(n) time and O(n^1/2) extra space to pre-process the input, and you're then allowed O(n^1/2) time to answer each of any number of queries that could then be sent your way.

Group the input by chunks of O(n^1/2), and store the sum of each (chunk 0: sum of arr[0] through arr[sqrt(n)-1]; chunk 1: sum of arr[sqrt(n)] through arr[2*sqrt(n)-1]; etc.). That's your preprocessing step.

Now, each query is the sum of some number (maybe 0) of complete chunks of size O(n^1/2) plus possibly parts of the two chunks on each end of the range. There are at most O(n^1/2) complete chunks to sum that are part of the range. Now consider the two chunks that are partially covered by the range. Each of these 2 chunks has at most O(n^1/2) numbers, so we can just add the individual numbers to the total and still keep the time within O(n^2).

This analysis assumes that adds are O(1).

are you posting this because you are taking parallel computing course in U of M?

I am taking it too and this looks quite the same as the homework........so, i wish i could help, but i dont want to

can be done using segment trees. See:
community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
O(preprocessing: n, query: n^1/2)

This is RMQA problem. This can be done by dividing the array in to n^1/2 parts. i.e, if array has 9 elements {3, 9, 5, 2, -1, 4, 10, 0, 3} Then partition the array in to 3 parts and store min for each part in an array M. so M[0] will have 3 , M[1] will have -1 and M[2] will have 0. If the range is 2 to 6 then we need to get min of a[2], M[1], a[6]. so this is O(n^1/2) space and O(n^1/2) time complexity.