What do we call a dynamic programic construct that allows us to compute sums of any range in logarithmic time?

Question

I was usually calling it ‘partial sums’, but I dunno how is it ‘officially’ called, and I have the impression it is not ‘partial sums’.

Anyway, the concept is pretty simple. Say you have an array of 8 elements, [3, 7, 2, 1, 5, 6, 9, 4]. You compute sums like that:

Of course, this will lead to an array of arrays of this form:

Now if we are asked, for example, what is the sum of elements of indexes from 0 till 4 we won’t linearily calculate that sum, but instead we will know it is equal to the sum of elements from 0 till 3 (which is 13) and then logarithmically go down till the element 5. So, the answer is: 18.

How should I call such a construct so that other peaople know what I’m talking about without drawing tables like these?

Answer 1

It seems like some partitioning.

Storing cumulative sums allows calculation of sum of consecutive elements in constant time and takes same amount of memory (n). Let i'th element of C be sum of all elements with with index <= i. Than sum of elements from index a till index b is C[b] - C[a].

Answer 2

Its called a Segment Tree and is usually used to handle queries faster.