Prefix Sum — A Complete Guide
Difference between en4 and en5, changed 3692 character(s)
↵
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 updates 
in 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 with mMultiple 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 &mdash; Static Range Sum Queries](https://cses.fi/problemset/task/1646) — Direct application of prefix sum↵
- [CSES &mdash; Subarray Sums I](https://cses.fi/problemset/task/1660) — Prefix sum with target finding↵
- [Codeforces 816B &mdash; Karen and Coffee](https://codeforces.me/problemset/problem/816/B) — Range updates with difference array↵
↵
### Medium↵
- [CSES &mdash; Subarray Divisibility](https://cses.fi/problemset/task/1662) — Prefix sum with modular arithmetic↵
- [CSES &mdash; 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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Nourhan_Abo-Heba 2026-03-11 15:26:53 3692
en4 English Nourhan_Abo-Heba 2025-09-14 18:46:28 6
en3 English Nourhan_Abo-Heba 2025-09-14 18:45:50 41
en2 English Nourhan_Abo-Heba 2025-09-14 17:03:56 106
en1 English Nourhan_Abo-Heba 2025-09-14 16:53:36 5501 Initial revision (published)