↵
Today we’'ll talk about **Prefix Sums** — one of the simplest and most powerful techniques in CP (Ccompetitive Pprogramming).↵
↵
---↵
↵
## 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:↵
↵
```cpp↵
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 = 1e6`0⁶ and `q = 1e6`0⁶ → **O(1e12)**0¹²) operations. fFar 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)```↵
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[r4] - p[l-1]↵
1] = 22 - 5 = 17↵
Check: 7 + 1 + 9 = 17 ✓↵
```↵
↵
---↵
↵
## Implementation ↵
↵
### First aAttempt (bBuggy with 0-indexing)↵
↵
```cpp↵
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)↵
↵
```cpp↵
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] = 0` is a safe base case.↵
* Time: O(n) preprocessing + O(1) per query↵
↵
---↵
↵
## When to uUse Prefix Sum?↵
↵
**Conditions:**↵
↵
1. Data must be **static** (no updatesin between queries).↵
2. 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]**.↵
↵
* Just build a prefix sum on the array.↵
* `ans = p[r] - p[l-1]` = number of```cpp↵
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.;↵
* Number of zeros? → `(r-l+1) - ans` 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`k appear in \[l..r]?”"**↵
↵
We can prepare **26 prefix arrays**, one for each letter.↵
↵
```cpp↵
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.↵
↵
```cpp↵
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:↵
↵
```cpp↵
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 withmMultiple tTest cCases:↵
↵
* Re-initializing `freq` every time = TLE.↵
↵
### Optimized Solution↵
↵
```cpp↵
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 (Partial SumDifference Array)↵
↵
Sometimes the problem is reversed:↵
*“ **"You’'re given many operations: add a value `v`v to all elements in range \[l..r]. Output final array.”"**↵
↵
This is where **difference array (** (also called partial sum)** comes in:↵
↵
```cpp↵
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.↵
↵
---↵
↵
## Challenge Questions↵
↵
1. ↵
Given an array, answer how many times a number `x`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](https://cses.fi/problemset/task/1646) — Direct application of prefix sum↵
- [CSES — Subarray Sums I](https://cses.fi/problemset/task/1660) — Prefix sum with target finding↵
- [Codeforces 816B — Karen and Coffee](https://codeforces.me/problemset/problem/816/B) — Range updates with difference array↵
↵
### Medium↵
- [CSES — Subarray Divisibility](https://cses.fi/problemset/task/1662) — Prefix sum with modular arithmetic↵
- [CSES — Forest Queries](https://cses.fi/problemset/task/1652) — 2D prefix sum application↵
↵
---↵
↵
## Challenge Questions↵
↵
1. **Given an array, answer how many times a number x appears in range\[l..r] ,, where x is different for each query ..**↵
↵
2. ↵
Hint: Build a 2D structure or use coordinate compression with prefix sums.↵
↵
2. **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!
Today we
↵
---↵
↵
##
↵
Let
↵
```↵
{5, 7, 1, 9, 1, 8}↵
```↵
↵
and I ask you: *
↵
### Brute Force Solution
↵
```cpp↵
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";↵
}↵
```↵
↵
*
If
↵
We need something better. That
↵
---↵
↵
##
↵
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)
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[
Check: 7 + 1 + 9 = 17 ✓↵
```↵
↵
---↵
↵
##
↵
###
↵
```cpp↵
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!)↵
```↵
↵
###
↵
```cpp↵
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";↵
}↵
```↵
↵
↵
* Using
* `p[0] = 0` is a safe base case
* Time: O(n) preprocessing + O(1) per query↵
↵
---↵
↵
##
↵
**Conditions:**↵
↵
1. Data must be **static** (no updates
2. 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↵
↵
---↵
↵
##
↵
Suppose you have an array of 0s and 1s, and you want to know **how many ones** are in range
↵
* `ans = p[r] - p[l-1]` = number of
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
}↵
```↵
↵
**Key insight:** Prefix sum works for counting, not just summing values.↵
↵
---↵
↵
##
↵
Suppose I give you a string and queries like:
*“
↵
We can prepare **26 prefix arrays**, one for each letter.↵
↵
```cpp↵
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:
* Query:
↵
---↵
↵
##
↵
Given a matrix, we want the sum of any sub-rectangle.↵
↵
```cpp↵
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**.↵
↵
---↵
↵
##
↵
If we only need counts of numbers:↵
↵
```cpp↵
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
↵
↵
###
↵
```cpp↵
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.↵
↵
---↵
↵
##
↵
Sometimes the problem is reversed:
*“
↵
This is where **difference array
↵
```cpp↵
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.↵
↵
---↵
↵
##
↵
1. ↵
Given an array, answer how many times a number `x`
↵
| 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](https://cses.fi/problemset/task/1646) — Direct application of prefix sum↵
- [CSES — Subarray Sums I](https://cses.fi/problemset/task/1660) — Prefix sum with target finding↵
- [Codeforces 816B — Karen and Coffee](https://codeforces.me/problemset/problem/816/B) — Range updates with difference array↵
↵
### Medium↵
- [CSES — Subarray Divisibility](https://cses.fi/problemset/task/1662) — Prefix sum with modular arithmetic↵
- [CSES — Forest Queries](https://cses.fi/problemset/task/1652) — 2D prefix sum application↵
↵
---↵
↵
## Challenge Questions↵
↵
1. **Given an array, answer how many times a number x appears in range
↵
↵
2. **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↵
```↵
↵
↵
↵
---↵
↵
## 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
↵
---↵
↵
↵
↵
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!



