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. 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]

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

Prefix sums are an essential tool that will appear again in many problems (range queries, strings, matrices, frequency counting, range updates…).