There are ten elements. Imagine a 0 that precedes this list.
0 + 5 + 2 = 7 is the next prefix sum.
0 + 5 + 2 + -6 = 1 is the prefix sum after.
0 + 5 + 2 + -6 + 8 = 9 is the new prefix sum.
This running total typically continues until the last element, 7, in the given list. The second sequence (list) has the prefix sums of eleven elements. The first element in the prefix sums array (second sequence) is the assumed (imagined) zero. The following two tables, where the second row for each table has the zero-based array indexes, illustrate these two sequences:
| Given Table | ||||||||||
| 5 | 2 | -6 | 8 | -4 | 0 | 9 | 3 | -1 | 7 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| Prefix Sums Table | ||||||||||
| 5 | 7 | 1 | 9 | 5 | 5 | 14 | 17 | 16 | 23 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
The first table is for the given array and the second table is for the prefix sums array. If the number of elements in the given array is n, then the number of elements in the prefix sums array is n+1. This article explains the main features of prefix sums. In this context, “pre-” means what has been added before. It can also mean prefixing the prefix array with zero.
Brute Force
A programmer should know the meaning of brute force as used in programming. Brute force means solving a problem using a direct algorithm, which is usually not as efficient (to use less time and memory) as another carefully taught algorithm.
Prefix Sum by Brute Force
In order to produce the prefix sums array, by brute force, for the above-given array, 5 will first be noted as the first prefix sum. Then 5 and 2 will be added to give the next prefix sum, 7. Then 5, 2, and -6 will be added to provide the prefix sum after 1. Next, 5, 2, -6, and 8 will be added to give the new prefix sum, 9, and so on. This procedure can be tiring.
Tiring or not, the code to produce the prefix sum array, from the assumed zero, by brute force is:
int A[] = {5, 2, -6, 8, -4, 0, 9, 3, -1, 7};
int P[n+1];
P[0] = 0;
for (int i=0; i<n; i++) {
int sum = 0;
int j;
for (j=0; j<i+1; j++) {
sum = sum + A[j];
}
P[j] = sum;
}
The outer for-loop iterates from 0 to just less than n. The inner for-loop iterates from 0 to i, the iteration index of the outer loop. With this, there are 55 main operations. The time complexity for this is O(n.log2n).
Prefix Sums in Linear Time
The previous time complexity is approximately O(n.log2n). The algorithm can be improved such that the sums are produced in linear time for time complexity, O(n). Prefix in this context means adding the sum of all the previous elements to the current given element. Consider the previous two tables, drawn as one table, with some modifications:
| Prefix Sums Table | ||||||||||
| Given: | 5 | 2 | -6 | 8 | -4 | 0 | 9 | 3 | -1 | 7 |
| 0 + 5 = | 5 + 2 = | 7 + -6 = | 1 + 8 = | 9 + -4 = | 5 + 0 = | 5 + 9 = | 14+3 = | 17+ -1= | 16+7 = | |
| 0 | 5 | 7 | 1 | 9 | 5 | 5 | 14 | 17 | 16 | 23 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
The first row in this table has the given elements at their assigned positions. For the second and third rows, the starting zero is assumed. For the second and third rows, each element is equal to the sum of all the previous elements, plus the current element. The last row has the prefix sums array indexes (zero-based). Note that the prefix sums array is one element longer than the given array.
This algorithm produces the prefix sums array in linear time of O(n) time complexity. That is, there are approximately n operations. And the recommended prefix sum code in C++ for O(n) time complexity is:
int A[] = {5, 2, -6, 8, -4, 0, 9, 3, -1, 7};
int P[n+1];
P[0] = 0;
for (int i=1; i<n+1; i++) {
P[i] = P[i-1] + A[i-1];
}
Notice that there is no nested loop this time. The statements inside the parentheses of the for-loop are essential. The main operation of the for-loop body is also important. As before, the for-loop iterates from 1 to less than n+1 and not from 0 to less than n. The statement of the for-loop body is:
This means that the current value of the given array is added to the previous prefix sum to provide the current prefix sum.
Common Problem for Prefix Sums
Notice that the corresponding index of the prefix sums array has 1 added to it compared to that of the given array.
A common problem for prefix sums is to find the sum of a sub-array of consecutive elements efficiently. This is the sum of a slice. The word “efficiently” means that a brute force algorithm is not to be used. The limiting indexes for the sub-array are x and y. Consider the given list:
The sum of the sub-array from element 8 to element 9 is:
8 is at index 3, for x; and 9 is at index 6 for y. The efficient way to do this is to subtract the prefix sum at index 2, for the given array, from the prefix sum at index 6 for the given array. For the prefix array, these are index y+1 and index x. The 1 to be added is removed to get the prefix array index, shown below, and the efficient code is:
int A[] = {5, 2, -6, 8, -4, 0, 9, 3, -1, 7};
int P[n+1];
P[0] = 0;
int x=3, y=6;
for (int i=1; i<n+1; i++) {
P[i] = P[i-1] + A[i-1];
}
int sliceSum = P[y+1] - P[x];
cout<<sliceSum<<endl;
The output is 13, as expected, but from an efficient code.
Conclusion
The prefix sums are the running totals of the elements of an array. Two arrays are involved: the given array and the produced prefix sums array. The prefix sums array is longer than the given array by one element. The main operation to obtain the elements of the prefix array is: the current value in the prefix sums array is the previous prefix sum, plus the current value of the given array. To obtain the sum of a slice from the given array, use: int sliceSum = P[y+1] – P[x];
Where x is the lower limit index of the slice in the given array, and y is the upper limit index of the slice in the given array.
