Today we'll talk about Prefix Sums — one of the simplest and most powerful techniques in competitive programming.
Problem Motivation
Let's say I give you an array:
{5, 7, 1, 9, 1, 8}
and I ask you: "What's the sum of elements in a specific range [l..r]?"
Brute Force Solution
int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
int q; cin >> q;
while(q--){
int l, r; cin >> l >> r;
int ans = 0;
for (int i = l; i <= r; i++){
ans += v[i];
}
cout << ans << "\n";
}
Time complexity: O(n × q).
If n = 10⁶ and q = 10⁶ → O(10¹²) operations. Far too slow (will never finish in time).
We need something better. That's where Prefix Sum comes in.
Prefix Sum Idea
Instead of recomputing sums for every query, we preprocess:
p[i] = v[1] + v[2] + ... + v[i]
Each query can then be answered in O(1):
sum(l..r) = p[r] - p[l-1]
Why Does This Work?
Array: [5, 7, 1, 9, 1, 8]
Prefix: [5, 12, 13, 22, 23, 31]
Query: sum from index 2 to 4
Answer = p[4] - p[1] = 22 - 5 = 17
Check: 7 + 1 + 9 = 17 ✓
Implementation
First Attempt (Buggy with 0-indexing)
int n; cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
vector<int> p(n);
for(int i = 0; i < n; i++) p[i] = v[i] + p[i-1];
// Problem when i=0 → p[-1] (invalid!)
Correct Implementation (1-indexed arrays)
int n; cin >> n;
vector<int> v(n+1), p(n+1);
v[0] = p[0] = 0;
for(int i = 1; i <= n; i++) cin >> v[i];
for(int i = 1; i <= n; i++) p[i] = v[i] + p[i-1];
int q; cin >> q;
while(q--){
int l, r; cin >> l >> r;
cout << p[r] - p[l-1] << "\n";
}
Notice:
- Using 1-indexing avoids the negative index bug
p[0] = 0is a safe base case- Time: O(n) preprocessing + O(1) per query
When to Use Prefix Sum?
Conditions:
- Data must be static (no updates between queries)
- The operation must have an inverse (like addition/subtraction)
Use cases:
- Range sum queries
- Range count queries
- Frequency queries in ranges
- 2D rectangle sum queries
Example 1: Count Ones in a Binary Array
Suppose you have an array of 0s and 1s, and you want to know how many ones are in range [l..r].
int n; cin >> n;
vector<int> v(n+1), p(n+1);
v[0] = p[0] = 0;
for(int i = 1; i <= n; i++) cin >> v[i];
for(int i = 1; i <= n; i++) p[i] = p[i-1] + v[i];
int q; cin >> q;
while(q--){
int l, r; cin >> l >> r;
int ones = p[r] - p[l-1];
int zeros = (r - l + 1) - ones;
cout << "Ones: " << ones << ", Zeros: " << zeros << "\n";
}
Key insight: Prefix sum works for counting, not just summing values.
Example 2: Count Letters in a String
Suppose I give you a string and queries like: "How many times does letter k appear in [l..r]?"
We can prepare 26 prefix arrays, one for each letter.
int n; cin >> n;
string s; cin >> s;
s = " " + s; // make it 1-indexed
vector<vector<int>> pref(26, vector<int>(n+1, 0));
// build prefix for each letter
for(int i = 0; i < 26; i++){
for(int j = 1; j <= n; j++){
int idx = s[j] - 'a';
pref[i][j] = pref[i][j-1] + (i == idx);
}
}
int q; cin >> q;
while(q--){
int l, r; char c; cin >> l >> r >> c;
int idx = c - 'a';
cout << pref[idx][r] - pref[idx][l-1] << "\n";
}
Complexity:
- Preprocessing: O(26 × n)
- Query: O(1)
Example 3: 2D Prefix Sum (Sum in Rectangle)
Given a matrix, we want the sum of any sub-rectangle.
int n, m; cin >> n >> m;
vector<vector<int>> v(n+1, vector<int>(m+1, 0));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> v[i][j];
// Build prefix sum
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
}
}
int q; cin >> q;
while(q--){
int xs, ys, xe, ye;
cin >> xs >> ys >> xe >> ye;
int ans = v[xe][ye] - v[xe][ys-1] - v[xs-1][ye] + v[xs-1][ys-1];
cout << ans << "\n";
}
Visual Explanation
To get sum of rectangle (xs,ys) to (xe,ye):
ans = [full rectangle to (xe,ye)]
- [rectangle to (xe, ys-1)]
- [rectangle to (xs-1, ye)]
+ [rectangle to (xs-1, ys-1)] // added back (was subtracted twice)
This technique is often called 2D Prefix Sum.
Example 4: Frequency Array
If we only need counts of numbers:
int n; cin >> n;
vector<int> v(n), freq(1e5+1, 0);
for(int i=0;i<n;i++) cin >> v[i], freq[v[i]]++;
int q; cin >> q;
while(q--){
int x; cin >> x;
cout << freq[x] << "\n";
}
Problem with Multiple Test Cases
Re-initializing freq every time = TLE.
Optimized Solution
vector<int> freq(1e5+1, 0);
int t; cin >> t;
while(t--){
int n; cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
freq[v[i]] = 0; // reset only used values
}
for(int i=0;i<n;i++) freq[v[i]]++;
int q; cin >> q;
while(q--){
int x; cin >> x;
cout << freq[x] << "\n";
}
}
Key optimization: Only reset values that were actually used, not the entire array.
Example 5: Range Updates (Difference Array)
Sometimes the problem is reversed: "You're given many operations: add a value v to all elements in range [l..r]. Output final array."
This is where difference array (also called partial sum) comes in:
int n, q; cin >> n >> q;
vector<int> diff(n+2, 0);
while(q--){
int l, r, val; cin >> l >> r >> val;
diff[l] += val;
diff[r+1] -= val;
}
// build final array
vector<int> arr(n+1);
arr[1] = diff[1];
for(int i=2;i<=n;i++) arr[i] = arr[i-1] + diff[i];
for(int i=1;i<=n;i++) cout << arr[i] << " ";
How It Works
Operation: add 5 to range [2, 4]
diff[2] += 5 → effect starts at index 2
diff[5] -= 5 → effect ends after index 4
After all operations, build prefix sum of diff array
→ gives final array values
Use case: When you have many range updates but only need the final state.
Complexity Comparison
| Approach | Preprocessing | Per Query | Total (q queries) |
|---|---|---|---|
| Brute Force | O(1) | O(n) | O(n × q) |
| Prefix Sum | O(n) | O(1) | O(n + q) |
For n = 10⁶, q = 10⁶: - Brute Force: 10¹² operations (too slow) - Prefix Sum: 2×10⁶ operations (fast)
Practice Problems
Easy
- CSES — Static Range Sum Queries — Direct application of prefix sum
- CSES — Subarray Sums I — Prefix sum with target finding
- Codeforces 816B — Karen and Coffee — Range updates with difference array
Medium
- CSES — Subarray Divisibility — Prefix sum with modular arithmetic
- CSES — Forest Queries — 2D prefix sum application
Challenge Questions
- Given an array, answer how many times a number x appears in range [l..r], where x is different for each query.
Hint: Build a 2D structure or use coordinate compression with prefix sums.
- What if you are asked to add values to a range like:
A[l] += v A[l+1] += 2*v A[l+2] += 3*v ... A[r] += (r-l+1)*v
Hint: Use difference array with arithmetic progression properties.
Summary
| Technique | Use Case | Preprocessing | Query |
|---|---|---|---|
| 1D Prefix Sum | Range sum queries | O(n) | O(1) |
| 2D Prefix Sum | Rectangle sum queries | O(n×m) | O(1) |
| Multiple Prefix Arrays | Count specific elements in range | O(k×n) | O(1) |
| Difference Array | Multiple range updates, single output | O(1) per update | O(n) final build |
Prefix sums are an essential tool that will appear again in many problems: range queries, strings, matrices, frequency counting, range updates, and more.
Master this technique, and you'll solve a whole class of problems effortlessly.
Next topics to explore: - Sparse Table for range minimum queries - Segment Trees for dynamic range queries - Fenwick Trees (Binary Indexed Trees) for updates and queries
Questions? Drop them in the comments!




