Prefix Sums

Precomputation for fast queries

If you need the sum of one array range only once, an ordinary loop is enough. But if there are many such queries, repeatedly traversing the same elements becomes unnecessary work. Prefix sums move part of the computation into a preprocessing step.

We create a prefix array where each element stores the sum of all values before the current position. It is convenient to make it one cell longer than the original array:

int[] prefix = new int[numbers.length + 1];

for (int i = 0; i < numbers.length; i++) {
    prefix[i + 1] = prefix[i] + numbers[i];
}

Now prefix[k] contains the sum of the first k elements. For example, prefix[0] is zero, while prefix[3] is the sum of the elements at indexes 0, 1, and 2.

A range sum through subtraction

To get the sum of elements from index left inclusive to right exclusive, it is enough to subtract two prefixes:

int rangeSum = prefix[right] - prefix[left];

prefix[right] contains all elements before the right boundary, while prefix[left] removes the part before the left boundary. After preprocessing, each such query takes O(1) time.

The cost of preprocessing

Building prefix sums requires O(n) time and O(n) extra space. This is useful when many queries must be answered for the same array after preprocessing. For a single query, an ordinary traversal may be simpler.