2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.