[Solved]: Can we compute the sum of a range of entries in $O(1)$ time?

Problem Detail: 

I have encountered a few tests in algorithms which ask for a data structure which allows to get the sum of all the elements of an array in the range [i..j], in O(1) time.

Is it even possible to do so?

Asked By : Trinarics

Answered By : sai_preet

Yes, calculation of range sum is possible in O(1) time. Suppose the data is given in an array. You need to preprocess the array to find the prefix sums. For this you need another array. To find range sum S(i,j] you need to compute P[j]-P[i]. Where P[j] and P[i] are entries of prefix sum array. For example, the given array is: 4 5 -2 5 -77 45. Corresponding prefix sum array is: 4 9 7 12 -65 -20. So, S(2, 4] = -65 - 7 = -72 (Sum from 2 to 4, 2 excluded and zero based indexing)

Note: We preprocess the given data to build the prefix sum array which takes O(n) time where n is the number of entries. After that, each query of the form S(i,j] takes O(1) time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25800

 Ask a Question

 Download Related Notes/Documents