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
size(a) + 1) that stores the sums of the prefixes of the initial array. More formally
sums[i] = a + a + ... 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
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?