1D Prefix Sum
I. In-Class Exercises
Programming Exercises
II. Knowledge Summary
✨ Core Idea of 1D Prefix Sum
Suppose you have an array and need to query the sum of elements in different ranges multiple times. If you add up from scratch each time, a single query takes O(n) time, and m queries take O(n*m) — very inefficient for large datasets.
1D Prefix Sum is designed to solve this problem — with a single O(n) preprocessing step, every subsequent range sum query takes only O(1) time.
✨ How to Compute the 1D Prefix Sum
Suppose we have an array array of length n. We define a prefix sum array prefix_sum, also of length n, where prefix_sum[i] represents the sum of all elements from the 1st to the i-th element of array. We use a recurrence formula to compute prefix_sum.
The recurrence formula is:
prefix_sum[i] = prefix_sum[i-1] + array[i]
prefix[0] = 0;
for (int i = 0; i < n; ++i) {
prefix[i] = prefix[i - 1] + array[i];
}✨ Complexity Analysis of 1D Prefix Sum
Complexity:
- Time Complexity: O(n) (preprocessing), O(1) (per range query)
- Space Complexity: O(n)
✨ Applications of 1D Prefix Sum
Range Sum Query on a 1D Array
Given an array array and its prefix sum prefix_sum, to compute the range sum of any interval, you only need the start and end of the interval to compute the range sum in O(1) time.
int l = 1; // Range start
int r = 3; // Range end
int sum_lr = prefix_sum[r] - prefix_sum[l - 1];Maximum Subarray Sum
Use a max_sub_sum variable to track the maximum subarray sum up to the current position i, and a min_prefix variable to track the minimum prefix sum up to the current position i.
for (int i = 1; i <= n; ++i) {
max_sub_sum = max(prefix[i] - min_prefix, max_sub_sum);
min_prefix = min(prefix[i], min_prefix);
}✨ Execution Example of 1D Prefix Sum
Problem: Given the array array = {0, 3, 1, 4, 1, 5} (1-indexed, array[0] is unused), find the range sum from the 2nd to the 4th element.
Step 1: Build the prefix sum array
| i | array[i] | Computation | prefix[i] |
|---|---|---|---|
| 0 | - | Initial value | 0 |
| 1 | 3 | prefix[0] + array[1] = 0 + 3 | 3 |
| 2 | 1 | prefix[1] + array[2] = 3 + 1 | 4 |
| 3 | 4 | prefix[2] + array[3] = 4 + 4 | 8 |
| 4 | 1 | prefix[3] + array[4] = 8 + 1 | 9 |
| 5 | 5 | prefix[4] + array[5] = 9 + 5 | 14 |
Step 2: Query the sum of range [2, 4]
Range sum = prefix[4] - prefix[2-1] = prefix[4] - prefix[1] = 9 - 3 = 6
Verification: array[2] + array[3] + array[4] = 1 + 4 + 1 = 6 ✓
Key insight: prefix[r] stores the sum of the first r elements. Subtracting prefix[l-1] (the sum of the first l-1 elements) leaves exactly the sum of elements from the l-th to the r-th.
✨ Detailed Problem-Solving Steps: Maximum Subarray Sum
Problem: Given an array, find a contiguous subarray with the maximum sum.
Thought process:
Step 1: Brute-force approach. Enumerate all intervals [l, r], compute the sum of each interval, and take the maximum. Time complexity O(n²) or O(n³).
Step 2: Prefix sum optimization. Any range sum = prefix[r] - prefix[l-1]. To maximize the range sum, we need to maximize prefix[r] - prefix[l-1].
Step 3: Key observation. For a fixed right endpoint r, prefix[r] is fixed. To maximize the difference, we only need to minimize prefix[l-1]. So during traversal, we maintain a "minimum prefix sum so far."
Step 4: Execution demonstration. Using array = {2, -3, 1, 4, -1} as an example:
| i | array[i] | prefix[i] | min_prefix | prefix[i]-min_prefix | max_sub_sum |
|---|---|---|---|---|---|
| 1 | 2 | 2 | 0 | 2-0=2 | 2 |
| 2 | -3 | -1 | 0 | -1-0=-1 | 2 |
| 3 | 1 | 0 | -1 | 0-(-1)=1 | 2 |
| 4 | 4 | 4 | -1 | 4-(-1)=5 | 5 |
| 5 | -1 | 3 | -1 | 3-(-1)=4 | 5 |
Final result: The maximum subarray sum is 5, corresponding to the subarray [1, 4] (range [3,4]), i.e., prefix[4] - prefix[2] = 4 - (-1) = 5.
✨ Common Mistakes with 1D Prefix Sum
- Index offset error: The range sum formula is
prefix[r] - prefix[l-1]— note that we subtract l-1, not l. Writingprefix[r] - prefix[l]would miss one element. - Forgetting to initialize prefix[0] to 0: prefix[0] = 0 is the foundation of prefix sums. Forgetting to set it will cause errors when querying ranges that include the first element.
- Confusion about whether indices start from 0 or 1: Prefix sums are usually more convenient with 1-based indexing (prefix[0]=0 serves as a sentinel). If using 0-based indexing, additional boundary handling is needed.
- Data overflow: Prefix sums can be very large. If the original array has 10^5 elements, each up to 10^9, the prefix sum can reach 10^14 — use the long long type.
✨ Application of Prefix Sum in Counting Sort (Advanced Content)
The following content should be read after learning about counting sort.
The key question in counting sort is: given how many times each number appears, how do we determine the position of each number in the sorted result? This is exactly what prefix sums can solve.
Principle:
- First count the occurrences of each value and store them in a counting array
cnt - Compute the prefix sum of
cnt. Nowcnt[v]means "how many elements have a value ≤ v," which is the last position of value v in the sorted result - Traverse the original array from back to front, placing each element at the position indicated by
cnt, then decrementcnt
Example: Sort the array {3, 1, 2, 1, 3} in ascending order
| Step | Description |
|---|---|
| Count occurrences | cnt = {0, 2, 1, 2} (1 appears 2 times, 2 appears 1 time, 3 appears 2 times) |
| Prefix sum | cnt = {0, 2, 3, 5} (≤1: 2, ≤2: 3, ≤3: 5) |
| Place elements | From back to front: arr[4]=3 → ans[4], arr[3]=1 → ans[1], arr[2]=2 → ans[2], arr[1]=1 → ans[0], arr[0]=3 → ans[3] |
| Sorted result | ans = {1, 1, 2, 3, 3} |
To sort in descending order, simply change the prefix sum to a suffix sum (accumulate from right to left). Now
cnt[v]represents "how many elements have a value ≥ v."
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9 int n;
10 cin >> n;
11 for (int i = 0; i < n; ++i) {
12 cin >> arr[i];
13 ++cnt[arr[i]];
14 }
15 for (int i = 2; i <= 100; ++i) {
16 cnt[i] += cnt[i - 1];
17 }
18 for (int i = n - 1; i >= 0; --i) {
19 ans[--cnt[arr[i]]] = arr[i];
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << ans[i] << (i + 1 == n ? "\n" : " ");
23 }
24
25 return 0;
26}1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9 int n;
10 cin >> n;
11 for (int i = 0; i < n; ++i) {
12 cin >> arr[i];
13 ++cnt[arr[i]];
14 }
15 for (int i = 99; i >= 1; --i) {
16 cnt[i] += cnt[i + 1];
17 }
18 for (int i = n - 1; i >= 0; --i) {
19 ans[--cnt[arr[i]]] = arr[i];
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << ans[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}