World's most popular travel blog for travel bloggers.

# [Solved]: Looking for the English name of algorithm using a precomputed array for interval sum computation

, ,
Problem Detail:

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 + 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 `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?

###### Asked By : Ivaylo Strandjev

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