Nourhan_Abo-Heba's blog

By Nourhan_Abo-Heba, history, 14 months ago, In English

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] = 0 is a safe base case
  • Time: O(n) preprocessing + O(1) per query

When to Use Prefix Sum?

Conditions:

  1. Data must be static (no updates 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].

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

Medium


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.

Hint: Build a 2D structure or use coordinate compression with prefix sums.

  1. 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!

  • Vote: I like it
  • +13
  • Vote: I do not like it

| Write comment?
»
14 months ago, hide # |
 
Vote: I like it -33 Vote: I do not like it

Prefix sum is very useless strong people use segment trees which have no downsides lol dont learn it

  • »
    »
    14 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like 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.)

  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    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?

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.