Prefix Sum

Revision en1, by Nourhan_Abo-Heba, 2025-09-14 16:53:36

Today we’ll talk about Prefix Sums — one of the simplest and most powerful techniques in CP (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 = 1e9 and q = 1e9 → O(1e18) operations. Impossible.

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]


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] = 0 is a safe base case.

When to use Prefix Sum?

Conditions:

  1. Data must be static (no updates in between queries).
  2. The operation must have an inverse (like addition/subtraction).

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 ones.
  • Number of zeros? → (r-l+1) - ans.

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";
}
  • 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";
}

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

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";
    }
}

Example 5: Range Updates (Partial Sum)

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 (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];

Challenge Questions

  1. Given an array, answer how many times a number x appears in range [l..r] ,x is different for each query .

  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

Can you adapt prefix sums / difference arrays to solve this efficiently?


That’s all for Lecture 3. Prefix sums are an essential tool that will appear again in many problems (range queries, strings, matrices, frequency counting, range updates…).


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)