Challenge problem 1

First, I will give you an array of integers (of length about 1000). The array may look something like this:

-1

Then you (your program, to be precise) will have some time to do pre-processing on the array. You can modify the array in any way you want, create new arrays, etc.

After the pre-processing is done, I will ask you some questions. Each question will be of the form "A B", where A and B are indices in the array (for example, "0 2"). For each question, your program needs to return to me the sum of the integers in the array between locations A and B (inclusive). In this case, for the question "0 2", the answer is "9" (= 3 + -1 + 7).

The tricky part is that you can only spend constant time per question. This means that you can not simply have a for loop to add up the entries from A to B - that would take linear time in the size of the array.

How would you do this? If there are several ways, pick the one that minimizes the pre-processing time. It is possible to do this with O(n) pre-processing and no additional memory (except for the original array and a few variables).