Imagine you have an array filled with numbers, say [1, 2, 3, 4, 5]. Now, the teacher asks you a problem: “Quickly calculate the sum from the 2nd number to the 4th number?”
You might think, “That’s easy! Just add 2 + 3 + 4, which equals 9.” But if the teacher asks for the sum from the 1st to the 5th number, or from the 3rd to the 100th number, or even “1000 such questions”, calculating each time from scratch would be very cumbersome. Is there a smarter way?
That’s where the prefix sum array comes in!
What is a Prefix Sum Array?¶
A Prefix Sum Array is an auxiliary array where each element represents the sum of the first few elements of the original array.
For example, given the original array A = [1, 2, 3, 4, 5], we construct a prefix sum array S where:
- S[0] = 0 (represents the sum of the first 0 elements, an initial value)
- S[1] = A[1] = 1 (sum of the first 1 element)
- S[2] = A[1] + A[2] = 1 + 2 = 3 (sum of the first 2 elements)
- S[3] = A[1] + A[2] + A[3] = 1 + 2 + 3 = 6 (sum of the first 3 elements)
- S[4] = A[1] + A[2] + A[3] + A[4] = 1 + 2 + 3 + 4 = 10 (sum of the first 4 elements)
- S[5] = A[1] + A[2] + A[3] + A[4] + A[5] = 1 + 2 + 3 + 4 + 5 = 15 (sum of the first 5 elements)
Thus, the prefix sum array S is [0, 1, 3, 6, 10, 15].
How to Calculate Interval Sum with a Prefix Sum Array?¶
Suppose we want to calculate the sum of elements from the i-th to the j-th element in the original array (where 1 ≤ i ≤ j ≤ n, and n is the length of the original array).
By the definition of the prefix sum array:
- S[j] is the sum of the first j elements (i.e., A[1] + A[2] + ... + A[j])
- S[i-1] is the sum of the first i-1 elements (i.e., A[1] + A[2] + ... + A[i-1])
Subtracting these two sums gives the sum of elements from the i-th to the j-th element:
Interval Sum = S[j] - S[i-1]
Example Verification¶
Using the original array A = [1, 2, 3, 4, 5], calculate the sum of the interval [2, 4] (i.e., the 2nd to the 4th elements):
- Original array elements: A[2] = 2, A[3] = 3, A[4] = 4, sum = 2 + 3 + 4 = 9
- Prefix sum array S = [0, 1, 3, 6, 10, 15]
- Using the formula: S[4] - S[1] = 10 - 1 = 9, which is correct!
Why is Prefix Sum So Fast?¶
Without prefix sums, calculating an interval sum requires adding elements from the start to the end, with a time complexity of O(j - i + 1) (the length of the interval). For q queries, the total time is O(q * n).
With prefix sums:
- Preprocessing the prefix sum array takes O(n) time (traverse the original array once)
- Each interval sum query takes O(1) time (just one subtraction)
- Total time complexity is O(n + q), which is much faster than direct calculation!
Notes¶
- Index Alignment: Pay attention to the index correspondence between the original array and the prefix sum array. If the original array is 0-indexed (e.g.,
A[0] = 1,A[1] = 2), the prefix sum array definition changes slightly, but the core formula remains similar (interval sum = S[j+1] - S[i]). - Interval Validity: Ensure the query interval
[i, j]is valid (i ≥ 1,j ≤ n), otherwise it will cause calculation errors. - Space vs. Time: The prefix sum array requires additional space with a space complexity of O(n), but this is traded for significant time optimization.
Summary¶
The prefix sum array is a simple yet powerful data structure. It precomputes cumulative sums to reduce interval sum queries from O(n) to O(1). The core idea is: using space to save time. Preprocess once, query in constant time—ideal for problems with multiple interval sum queries.
Now you should find prefix sums straightforward! Try constructing a prefix sum array with your own array and calculate several interval sums to experience its magic.