Prefix Sum — The Running Total

Real-world analogy

What is it?

A prefix sum is a pre-computed array where each element stores the cumulative sum of all elements from the beginning up to that position. By building this array once in O(n), you can answer any range sum query (what is the sum from index l to index r?) in O(1) time. This transforms slow repeated calculations into instant lookups.

Real-world relevance

Prefix sums are used in financial running balances (bank statements show running totals), in image processing (integral images for fast blur operations), in databases (cumulative aggregations), and in statistics (cumulative distribution functions). Any time you need running totals or range queries, prefix sums are the tool.

Key points

• What is Prefix Sum? — A prefix sum array stores the cumulative sum of elements from the start up to each position. For array [3, 5, 2, 8], the prefix sum is [3, 8, 10, 18]. prefix[i] = arr[0] + arr[1] + ... + arr[i]. It is like a running total.
• Building the Prefix Sum Array — Start by setting prefix[0] = arr[0]. Then for each i from 1 to n-1: prefix[i] = prefix[i-1] + arr[i]. Each element is the previous running total plus the current element. This takes O(n) time — just one pass through the array.
• Range Sum in O(1) — To find the sum of elements from index l to index r: sum = prefix[r] - prefix[l-1]. If l is 0, just use prefix[r]. This is O(1) — constant time, no matter how large the range! Without prefix sums, you would need O(n) to add up the range.
• Why Prefix Sum is Powerful — Imagine 100,000 queries each asking for the sum of a range. Without prefix sums: 100,000 * n operations. With prefix sums: n operations to build, then 100,000 * 1 to answer. For n = 100,000, that is 10 billion vs 200,000 operations!
• 1-Indexed Prefix Sum (Easier Formula) — Many programmers use 1-based indexing for prefix sums: prefix[0] = 0, prefix[i] = prefix[i-1] + arr[i] for i from 1 to n. Then sum from l to r = prefix[r] - prefix[l-1] works for ALL cases, even when l = 1. No special cases!
• Common Applications — Prefix sums are used in: range sum queries, finding subarrays with a given sum, calculating averages of subarrays, 2D prefix sums for matrix queries, and many optimization problems. It is one of the most useful CP techniques.
• Prefix Sum with Modulo — If the problem asks for sums modulo m, just apply modulo when building the prefix sum: prefix[i] = (prefix[i-1] + arr[i]) % m. Be careful with subtraction — (prefix[r] - prefix[l-1] + m) % m handles the case where the subtraction goes negative.
• Difference Array (Inverse of Prefix Sum) — A difference array is the inverse operation. If you need to add a value to all elements in a range [l, r], instead of updating each element, just add to diff[l] and subtract from diff[r+1]. Then take the prefix sum of diff to get the final array. This is O(1) per update!

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;           // n = number of elements, q = number of queries
    cin >> n >> q;

    // 1-indexed prefix sum (easier formula — prefix[0] = 0 avoids edge cases)
    vector<long long> arr(n + 1), prefix(n + 1, 0);  // prefix[i] will hold sum of arr[1..i]
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];                          // Read each element
        prefix[i] = prefix[i - 1] + arr[i];    // Running total: add current to previous sum
    }

    // Answer q range sum queries in O(1) each
    while (q--) {
        int l, r;
        cin >> l >> r;
        // Sum from l to r = (sum from 1 to r) minus (sum from 1 to l-1)
        long long rangeSum = prefix[r] - prefix[l - 1];
        cout << rangeSum << "\n";
    }

    return 0;
}

Line-by-line walkthrough

1. 1. vector prefix(n + 1, 0); — we create a prefix sum array of size n+1, filled with zeros. We use 1-based indexing with prefix[0] = 0 so the range sum formula works cleanly.
2. 2. prefix[i] = prefix[i - 1] + arr[i]; — each prefix sum entry equals the previous total plus the current element. After this loop, prefix[i] holds the sum of arr[1] through arr[i].
3. 3. long long rangeSum = prefix[r] - prefix[l - 1]; — the magic formula! The sum from l to r equals (sum from 1 to r) minus (sum from 1 to l-1). Two lookups and one subtraction — O(1)!
4. 4. We use long long because sums can get very large. If each element is up to 10^9 and we have 200,000 elements, the total sum could be up to 2 * 10^14, which overflows a 32-bit int.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    int arr[] = {2, 4, 6, 8, 10};
    int prefix[5];

    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }

    // Query: sum from index 0 to 3
    cout << prefix[3] << "\n"; // Correct: 20

    // Query: sum from index 2 to 4
    cout << prefix[4] - prefix[1] << "\n"; // Should be 6+8+10 = 24

    // Query: sum from index 0 to 0
    cout << prefix[0] - prefix[-1] << "\n"; // Just element 0 = 2

    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Prefix Sum Array (CP-Algorithms)
• Prefix Sums Tutorial (YouTube)
• Static Range Sum Queries (CSES)