Looking for the English name of algorithm using a precomputed array for interval sum computation

Question

I am looking for the English name of the following algorithm:

We are given an array a with numbers and we need to be able to efficiently retrieve the sum of a continuous interval [f,t] of numbers in that array. In order to do that we precompute an array sums(of size size(a) + 1) that stores the sums of the prefixes of the initial array. More formally sums[i] = a[0] + a[1] + ... a[i-1]. This array can be constructed with linear complexity and now in order to compute the sum of the numbers in the interval [f,t], we simply compute sums[t]-sums[f-1].

Direct translation of the name of the algorithm(or more precisely the datastructure) that I've seen used in Bulgaria is prefix array, but in my experience direct translation often turns out to be wrong when it comes to algorithms and data structures.

How is this algorithm(or datastructure) called in English?

Answer 1

I think the array sum is the result of the prefix computation of the original array (link).

Answer 2

The correct term is Prefix Sum. See e.g. https://en.wikipedia.org/wiki/Prefix_sum

Answer 3

I don't know if your algorithm has a name, however the maximum sum subsequence problem is very similar:

To solve the maximum sum problem one must locate the maximal sum sub-vector of an array $A$ of $n$ numbers. The maximal sub-vector of $A$ is the sub- vector $A[i, . . . , j]$ maximizing $\sum_{s=i}^j s$. The problem originates from Ulf Grenander who defined the problem in the setting of pattern recognition [1].

1. Bentley, J.: Programming pearls: algorithm design techniques. Commun. ACM 27(9) (1984) 865–873