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!








Prefix sum is very useless strong people use segment trees which have no downsides lol dont learn it
Using a segment tree is often overkill, not to mention prefix sums are a fundamental concept that can be useful when thinking of solutions to certain problems (especially when you need to do something like a prefix sum on the prefix sums [not 2D prefix sums] or a ST of prefix sums). Also, using a segment tree adds a log factor which can be the difference between AC and TLE on certain problems. (For example, if you need some static information as part of a calculation within Mo queries, using a ST instead will often lead to a TLE.)
What do you think of SOS DP then? Are you going to write a segment tree nested with segment tree nested with segment tree nested with segment tree nested with segment tree?
Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).
The guide on prefix sums is somewhat incomplete because it omits the 2D difference array. If anyone is interested, here’s a recent AtCoder problem I found: D-Clouds The editorial explains the idea very clearly, and that’s where I learned it.