How to improve time complexity of this algorithm

Question

Here's a simple problem: I have this array of length N, and a function that given 2 bounds (a,b) returns the sum of all the elements in the array between a and b.

Now, this is clearly O(N) time complexity... but if I wanted to make it more efficient (like log(N)), with a second data structure that stores partial sums, how could I accomplish it?

I was thinking of a binary tree but can't find an algorithm. Of course I could just create a NxN matrix but it's too much. I'd like something that doesn't require too much space and lets me have a logarithmic time complexity; any idea?

UPDATE: I didn't specify it clearly.. but:

1. the bounds are on the indexes of the array, not the values
2. the array is dynamic, values can change, and I don't want to have linear complexity to change a value! Therefore the simple algorithm of partial sums doesn't work, I think..
3. no concurrent programming (1 CPU)

Answer 1

Well, you can have another array of the same size where you store the partial sums. Then, whenever you are given the bounds you can just subtract the partial sums and you get the sum of elements in that interval. For example:

Elements:    1 2 3 4  5  6
Partial_Sum: 1 3 6 10 15 21

Lets, say that the array starts at index=0, and you want the sum of elements in the interval [1, 3] inclusive:

// subtract 1 from the index of the second sum, because we
// want the starting element of the interval to be included.
Partial_Sum[3] - Partial_Sum[1-1] = 10 - 1 = 9