What is the best algorithm for finding the sum of all elements in an arbitrary basement

Question

I have a problem and an OK-ish solution. I hope there will be a better solution.

Problem

I have an array containing about 200,000 integers. Given the two indexes, i1 and i2, I need to calculate the sum of all the elements between i1 and i2. Each integer in an array is 1 to 4 inclusive. For instance:

a = [1, 3, 2, 4, 3, 2, 4, 1]; subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2) 

This operation will be performed approximately 200,000 times, so it should be fairly quick. The simple counter in the for loop is O (n) and too slow. An array never changes after construction, so it must have a relatively expensive preprocessing step.

My best solution so far

This algorithm works in O (log n) time:

First enter the original array with zeros until its length is two. Then divide the array into two equal parts and save the sum of each of them. Then divide the array into quarters and save the sum of each of them. Then the eighth. Continue to do this until the array is partitioned into 2 element lengths. For the 8-element array above, this is done in two steps:

 halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])] quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])] 

Then, given the two indexes, you can now work out subsection_sum in O (log n) time. For example, subsection_sum (a, 2, 7) == quarters [1] + halves [1].

Answer 1

Enter an auxiliary array containing the cumulative amount. That is, element i auxiliary array has a sum of elements from 0 to i original array. The sum of the subaram is simply the difference of two elements from the auxiliary array. This will produce a result in constant time, O(1) .

It depends on the invariant of the subsection_sum function asked in the question:

 subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2) 

where I assume i1 <= i2 . Reordering, we have:

 subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1) 

Note that the amounts on the right-hand side begin with 0 . The auxiliary array can be considered as caching values ​​for sums from zero, subsection_sum(a, 0, i) for all i .

Answer 2

If you can afford the extra O(n) storage, you can create a lookup table whose element i th is the sum of elements with indices 0 through i (inclusive) in the input array. In pseudo code:

 def computeLookupTable(arr): let n = arr.length let lookupTable = new Array() lookupTable[0] = arr[0] for i=1 to n: lookupTable[i] = arr[i] + lookupTable[i-1] return lookupTable 

Then you can use this table to calculate the sum of all the elements in the array between i1 and i2 , taking the difference

 lookupTable[i2] - lookupTable[i1] 

which takes constant time.