15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A prefix sum array stores, at index i, the sum of every input value from index 0 through i. Build it in one pass with prefix[i] = prefix[i - 1] + A[i]. Then the sum of any range is prefix[right] minus prefix[left - 1]. Building costs O(n) time and space, and each query costs O(1).
| Prefix recurrence | prefix[0] = A[0]; prefix[i] = prefix[i - 1] + A[i] |
|---|---|
| Suffix recurrence | suffix[n - 1] = A[n - 1]; suffix[i] = A[i] + suffix[i + 1] |
| Range sum [left, right] | prefix[right], or prefix[right] - prefix[left - 1] when left > 0 |
| Build time | O(n), one pass |
| Query time | O(1), against O(m) for adding m values directly |
| Extra space | O(n) for the separate summary array |
You should already be comfortable with these array ideas:
0 through length - 1.0, 1, 2, ....length - 1, length - 2, ....Build a second array that stores running summaries.
A prefix sum at index i is the sum of every input value from index 0 through index i.
A suffix sum at index i is the sum of every input value from index i through the final index.
Preprocessing makes one pass to build a summary array. Each later range-sum query reads one or two stored values instead of adding every value in the range again.
Use this array throughout:
1index: 0 1 2 3
2A: [2, 4, 1, 3]Build its prefix-sum array, then find the inclusive sum from index 1 through index 3.
“Inclusive” means both boundary indices belong to the range. Range [1, 3] contains:
1index: 1 2 3
2A: [4, 1, 3]Its direct sum is 4 + 1 + 3 = 8.
Build this prefix array before answering the query:
1index: 0 1 2 3
2prefix: [2, 6, 7, 10]Each cell has this meaning:
1prefix[i] = sum of A[0] through A[i]Start with a prefix array of four unfilled cells:
Build prefix left to right: prefix[0] = 2, then 6, 7, 10. Any range sum is one subtraction: sum of A[1..3] = 10 − 2 = 8.
There is no earlier prefix cell before index 0. Index 0 is the base case.
prefix[0] represents the sum from A[0] through A[0].
The sum through index 1 consists of:
0, which is 2A[1], which is 4For range [1, 3], prefix[3] includes every value from index 0 through index 3:
1prefix[3] = 2 + 4 + 1 + 3 = 10The requested range starts at index 1. Values before index 1 end at index 0, and their total is prefix[0].
1sum[1, 3] = prefix[3] - prefix[0]
2 = 10 - 2
3 = 8Subtracting the prefix before left removes exactly the values outside the requested inclusive range.
After each prefix cell is computed, the following remains true:
After computing
prefix[i],prefix[i]equals the sum ofA[0]throughA[i]. Every earlier prefix entry is also correct and does not need to change.
This statement is the loop invariant for prefix construction.
The states establish it:
0, prefix[0] was exactly the sum through index 0.1, the correct total through 0 was extended by A[1].For a query [left, right], prefix[right] contains all values from 0 through right.
left = 0, that is exactly the requested range.left > 0, prefix[left - 1] contains exactly the values before left.left through right.Suffix sums apply the same recurrence from right to left:
1suffix[i] = sum of A[i] through A[n - 1]For the example:
1index: 0 1 2 3
2A: [2, 4, 1, 3]
3suffix: [10, 8, 4, 3]The final index is the suffix base case:
1suffix[3] = A[3] = 3Move left after establishing that base case:
1suffix[2] = A[2] + suffix[3] = 1 + 3 = 4
2suffix[1] = A[1] + suffix[2] = 4 + 4 = 8
3suffix[0] = A[0] + suffix[1] = 2 + 8 = 10To build prefix sums:
prefix[0].1 to the final index.The recurrence is:
1prefix[0] = A[0]
2prefix[i] = prefix[i - 1] + A[i] for i > 0To answer an inclusive range sum:
1if left = 0:
2 return prefix[right]
3
4otherwise:
5 return prefix[right] - prefix[left - 1]The left = 0 branch is necessary because there is no valid array cell at index -1.
To build suffix sums:
0.The recurrence is:
1suffix[n - 1] = A[n - 1]
2suffix[i] = A[i] + suffix[i + 1] for i < n - 1Use a prefix array for multiple range-sum queries on the same unchanged input. Direct calculation adds every element in the queried range each time. Prefix preprocessing performs those additions once and uses stored totals for later queries.
1function buildPrefixSums(A):
2 input:
3 A, an integer array of length n
4 returns:
5 a new integer array prefix of length n
6 mutation:
7 does not modify A
8
91. n ← length(A)
102. prefix ← new array of length n
113. if n = 0:
124. return prefix
135. prefix[0] ← A[0]
146. for i ← 1 to n - 1:
157. prefix[i] ← prefix[i - 1] + A[i]
168. return prefix1function rangeSumInclusive(prefix, left, right):
2 input:
3 prefix, a prefix-sum array for an original array of length n
4 left and right, inclusive integer indices
5 returns:
6 the sum of original-array values from left through right
7 mutation:
8 does not modify prefix
9 preconditions:
10 n > 0
11 0 ≤ left ≤ right < n
12 failure behavior:
13 reject the query if any precondition is false
14
151. n ← length(prefix)
162. if n = 0 or left < 0 or left > right or right ≥ n:
173. reject query
184. if left = 0:
195. return prefix[right]
206. return prefix[right] - prefix[left - 1]1function buildSuffixSums(A):
2 input:
3 A, an integer array of length n
4 returns:
5 a new integer array suffix of length n
6 mutation:
7 does not modify A
8
91. n ← length(A)
102. suffix ← new array of length n
113. if n = 0:
124. return suffix
135. suffix[n - 1] ← A[n - 1]
146. for i ← n - 2 down to 0:
157. suffix[i] ← A[i] + suffix[i + 1]
168. return suffixrangeSumInclusive has a helper contract: its prefix input must have been built from the same original array whose range is being queried.
Use the original input:
1index: 0 1 2 3
2A: [2, 4, 1, 3]Call:
1prefix ← buildPrefixSums(A)
2answer ← rangeSumInclusive(prefix, 1, 3)buildPrefixSums(A)Line 1
1n ← length(A) = 4Line 2
Allocate four prefix cells:
1prefix: [_, _, _, _]Line 3
n = 0 is false. Do not return.
Line 5
1prefix[0] ← A[0] = 2
2
3prefix: [2, _, _, _]Line 6, first iteration: i = 1
Line 7
1prefix[1] ← prefix[0] + A[1]
2 ← 2 + 4
3 ← 6
4
5prefix: [2, 6, _, _]Line 6, second iteration: i = 2
Line 7
1prefix[2] ← prefix[1] + A[2]
2 ← 6 + 1
3 ← 7
4
5prefix: [2, 6, 7, _]Line 6, third iteration: i = 3
Line 7
1prefix[3] ← prefix[2] + A[3]
2 ← 7 + 3
3 ← 10
4
5prefix: [2, 6, 7, 10]The next index would be 4, so the loop ends.
Line 8
1return [2, 6, 7, 10]rangeSumInclusive(prefix, 1, 3)Line 1
1n ← length(prefix) = 4Line 2
Check the conditions:
1n = 0 → false
2left < 0 → 1 < 0, false
3left > right → 1 > 3, false
4right ≥ n → 3 ≥ 4, falseThe query is valid.
Line 4
1left = 0
21 = 0The condition is false.
Line 6
1return prefix[right] - prefix[left - 1]
2 = prefix[3] - prefix[0]
3 = 10 - 2
4 = 8The inclusive sum from index 1 through index 3 is 8.
We prove that buildPrefixSums returns a correct prefix-sum array.
Initialization:
Before the loop starts, line 5 assigns:
1prefix[0] = A[0]So prefix[0] is the sum of A[0] through A[0]. The invariant is true for index 0.
Preservation:
Assume that before an iteration for index i, prefix[i - 1] equals the sum of A[0] through A[i - 1].
Line 7 computes:
1prefix[i] = prefix[i - 1] + A[i]Substituting the assumed meaning of prefix[i - 1] gives:
1prefix[i] = sum of A[0] through A[i - 1] + A[i]Therefore, prefix[i] is the sum of A[0] through A[i]. Earlier entries are unchanged, so they remain correct.
Termination:
The loop visits every index from 1 through n - 1. Combined with the base case at index 0, every prefix entry is correct when the loop ends. The returned array is a valid prefix-sum array.
Assume prefix is correct and the query satisfies:
10 ≤ left ≤ right < nIf left = 0, line 5 returns prefix[right]. By the prefix definition, that is the sum of A[0] through A[right], exactly the requested range.
If left > 0, line 6 returns:
1prefix[right] - prefix[left - 1]prefix[right] contains the sum of A[0] through A[right].
prefix[left - 1] contains the sum of A[0] through A[left - 1].
Subtracting removes exactly the elements before left, leaving the sum of A[left] through A[right]. The query result is correct.
For suffix sums, the direction changes because each cell needs the already-computed suffix to its right.
Initialization:
The final cell is assigned:
1suffix[n - 1] = A[n - 1]This value is the sum from the final index through itself.
Preservation:
Suppose suffix[i + 1] is the sum of A[i + 1] through A[n - 1]. The recurrence computes:
1suffix[i] = A[i] + suffix[i + 1]So suffix[i] becomes the sum of A[i] through A[n - 1].
Termination:
The loop moves left until it computes index 0. Every suffix entry has the required meaning.
Let n be the array length.
For prefix construction:
n > 0.1 through n - 1.That is one constant-time recurrence per array element, so building the prefix array takes:
1O(n) timeSuffix construction also performs one constant-time recurrence per element, so it also takes:
1O(n) timeFor a query beginning at index 0, the algorithm reads one prefix value and returns it.
For a query beginning after index 0, the algorithm reads two prefix values and performs one subtraction.
Both cases use a fixed number of operations:
1O(1) time per queryThe input array is not modified. The separate prefix array contains n entries:
1O(n) auxiliary spaceA separate suffix array also uses O(n) auxiliary space.
If a queried range contains m elements, directly adding its values performs m additions or visits proportional to m elements:
1O(m) time per direct range sumPrefix preprocessing spends O(n) time once, then each valid query takes O(1) time.
prefix[left - 1]Incorrect query line:
1return prefix[right] - prefix[left - 1]used even when left = 0.
Smallest exposing input:
1A = [2, 4, 1]
2range = [0, 1]The attempted calculation is:
1prefix[1] - prefix[-1]prefix[-1] is outside zero-based array bounds.
Correction:
1if left = 0:
2 return prefix[right]
3return prefix[right] - prefix[left - 1]Incorrect recurrence:
1prefix[i] = A[i - 1] + A[i]Exposing input:
1A = [2, 4, 1]The resulting state is:
1prefix[0] = 2
2prefix[1] = 2 + 4 = 6
3prefix[2] = 4 + 1 = 5
4
5prefix = [2, 6, 5]The sum through index 2 is 2 + 4 + 1 = 7, not 5.
Correction:
1prefix[i] = prefix[i - 1] + A[i]The previous prefix represents the total of all earlier values.
Incorrect direction:
1for i ← 0 to n - 2:
2 suffix[i] ← A[i] + suffix[i + 1]Exposing input:
1A = [2, 4, 1]At i = 0, this tries to read suffix[1] before it has been computed.
Correction:
1suffix[n - 1] ← A[n - 1]
2for i ← n - 2 down to 0:
3 suffix[i] ← A[i] + suffix[i + 1]Start with the final suffix value, then move right to left because each computation depends on the cell to its right.
Empty array
1A = []There is no prefix[0] and no suffix[n - 1]. Building either summary returns an empty array. Range queries must be rejected.
Single element
1A = [6]
2prefix = [6]
3suffix = [6]
4range [0, 0] = 6Range beginning at zero
1A = [2, 4, 1]
2prefix = [2, 6, 7]
3range [0, 2] = prefix[2] = 7No subtraction occurs.
Range containing one element away from index zero
1A = [2, 4, 1, 3]
2prefix = [2, 6, 7, 10]
3range [2, 2] = prefix[2] - prefix[1] = 7 - 6 = 1Invalid range
Reject either of these:
1left > right
2right ≥ lengthFor example:
1A = [2, 4, 1]
2range [2, 1] → reject
3range [0, 3] → rejectImplement buildPrefixSums and rangeSumInclusive for an integer array.
Executable tests check all valid ranges of empty-disallowed, single-element, and multi-element inputs, including ranges beginning at index zero.
1def build_prefix_sums(a):
2 n = len(a)
3 prefix = [0] * n
4 if n == 0:
5 return prefix
6 prefix[0] = a[0]
7 for i in range(1, n):
8 prefix[i] = prefix[i - 1] + a[i]
9 return prefix
10
11def range_sum_inclusive(prefix, left, right):
12 n = len(prefix)
13 if n == 0 or left < 0 or left > right or right >= n:
14 raise ValueError("invalid range")
15 if left == 0: # prefix[-1] would be out of bounds
16 return prefix[right]
17 return prefix[right] - prefix[left - 1]
18
19def build_suffix_sums(a):
20 n = len(a)
21 suffix = [0] * n
22 if n == 0:
23 return suffix
24 suffix[n - 1] = a[n - 1]
25 for i in range(n - 2, -1, -1): # right to left
26 suffix[i] = a[i] + suffix[i + 1]
27 return suffix
28
29A = [2, 4, 1, 3]
30prefix = build_prefix_sums(A)
31print("prefix =", prefix)
32print("sum[1, 3] =", range_sum_inclusive(prefix, 1, 3))
33print("sum[0, 2] =", range_sum_inclusive(prefix, 0, 2))
34print("sum[2, 2] =", range_sum_inclusive(prefix, 2, 2))
35print("suffix =", build_suffix_sums(A))1import java.util.Arrays;
2
3public class Main {
4 static int[] buildPrefixSums(int[] a) {
5 int n = a.length;
6 int[] prefix = new int[n];
7 if (n == 0) return prefix;
8 prefix[0] = a[0];
9 for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i];
10 return prefix;
11 }
12
13 static int rangeSumInclusive(int[] prefix, int left, int right) {
14 int n = prefix.length;
15 if (n == 0 || left < 0 || left > right || right >= n) {
16 throw new IllegalArgumentException("invalid range");
17 }
18 if (left == 0) return prefix[right]; // prefix[-1] would be out of bounds
19 return prefix[right] - prefix[left - 1];
20 }
21
22 static int[] buildSuffixSums(int[] a) {
23 int n = a.length;
24 int[] suffix = new int[n];
25 if (n == 0) return suffix;
26 suffix[n - 1] = a[n - 1];
27 for (int i = n - 2; i >= 0; i--) suffix[i] = a[i] + suffix[i + 1]; // right to left
28 return suffix;
29 }
30
31 public static void main(String[] args) {
32 int[] a = {2, 4, 1, 3};
33 int[] prefix = buildPrefixSums(a);
34 System.out.println("prefix = " + Arrays.toString(prefix));
35 System.out.println("sum[1, 3] = " + rangeSumInclusive(prefix, 1, 3));
36 System.out.println("sum[0, 2] = " + rangeSumInclusive(prefix, 0, 2));
37 System.out.println("sum[2, 2] = " + rangeSumInclusive(prefix, 2, 2));
38 System.out.println("suffix = " + Arrays.toString(buildSuffixSums(a)));
39 }
40}1#include <iostream>
2#include <stdexcept>
3#include <vector>
4using namespace std;
5
6vector<int> buildPrefixSums(const vector<int>& a) {
7 int n = a.size();
8 vector<int> prefix(n);
9 if (n == 0) return prefix;
10 prefix[0] = a[0];
11 for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i];
12 return prefix;
13}
14
15int rangeSumInclusive(const vector<int>& prefix, int left, int right) {
16 int n = prefix.size();
17 if (n == 0 || left < 0 || left > right || right >= n) throw invalid_argument("invalid range");
18 if (left == 0) return prefix[right]; // prefix[-1] would be out of bounds
19 return prefix[right] - prefix[left - 1];
20}
21
22vector<int> buildSuffixSums(const vector<int>& a) {
23 int n = a.size();
24 vector<int> suffix(n);
25 if (n == 0) return suffix;
26 suffix[n - 1] = a[n - 1];
27 for (int i = n - 2; i >= 0; i--) suffix[i] = a[i] + suffix[i + 1]; // right to left
28 return suffix;
29}
30
31void show(const vector<int>& a) {
32 cout << "[";
33 for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
34 cout << "]";
35}
36
37int main() {
38 vector<int> a = {2, 4, 1, 3};
39 vector<int> prefix = buildPrefixSums(a);
40 cout << "prefix = "; show(prefix); cout << "\n";
41 cout << "sum[1, 3] = " << rangeSumInclusive(prefix, 1, 3) << "\n";
42 cout << "sum[0, 2] = " << rangeSumInclusive(prefix, 0, 2) << "\n";
43 cout << "sum[2, 2] = " << rangeSumInclusive(prefix, 2, 2) << "\n";
44 cout << "suffix = "; show(buildSuffixSums(a)); cout << endl;
45}1function buildPrefixSums(a) {
2 const n = a.length;
3 const prefix = new Array(n).fill(0);
4 if (n === 0) return prefix;
5 prefix[0] = a[0];
6 for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i];
7 return prefix;
8}
9
10function rangeSumInclusive(prefix, left, right) {
11 const n = prefix.length;
12 if (n === 0 || left < 0 || left > right || right >= n) throw new RangeError('invalid range');
13 if (left === 0) return prefix[right]; // prefix[-1] would be out of bounds
14 return prefix[right] - prefix[left - 1];
15}
16
17function buildSuffixSums(a) {
18 const n = a.length;
19 const suffix = new Array(n).fill(0);
20 if (n === 0) return suffix;
21 suffix[n - 1] = a[n - 1];
22 for (let i = n - 2; i >= 0; i--) suffix[i] = a[i] + suffix[i + 1]; // right to left
23 return suffix;
24}
25
26const show = (a) => `[${a.join(', ')}]`;
27const A = [2, 4, 1, 3];
28const prefix = buildPrefixSums(A);
29console.log(`prefix = ${show(prefix)}`);
30console.log(`sum[1, 3] = ${rangeSumInclusive(prefix, 1, 3)}`);
31console.log(`sum[0, 2] = ${rangeSumInclusive(prefix, 0, 2)}`);
32console.log(`sum[2, 2] = ${rangeSumInclusive(prefix, 2, 2)}`);
33console.log(`suffix = ${show(buildSuffixSums(A))}`);A suffix sum at index i is the sum of A[i] through the last index. You build it right to left, because each cell needs the one to its right. For [2, 4, 1, 3] it is [10, 8, 4, 3].
It pays O(n) once so that every later range-sum query takes O(1). Adding a range of m values directly costs O(m) every time. The saving matters when many queries hit the same unchanged array.
Take prefix[right] and subtract prefix[left - 1], which removes the values before left. For range [1, 3] on [2, 4, 1, 3] that is 10 - 2 = 8. When left is 0, return prefix[right] directly.
There is no prefix[-1] to subtract. For range [0, 1] the formula would read prefix[-1], which is outside the array. Returning prefix[right] when left is 0 avoids it.
It goes stale. The lesson builds prefix sums for an unchanged input, so any change means rebuilding the array in O(n). With frequent changes between queries, rebuilding every time costs more than it saves.