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

, , No Comments
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[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?

Asked By : Ivaylo Strandjev

Answered By : Arrigo

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12330

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback