Prefix Sums

Quick Revisit

• USE WHEN: Multiple range-sum queries on a static array
• INVARIANT: pre[i] = a[0] + a[1] + ... + a[i-1]; range sum [l,r] = pre[r+1] - pre[l]
• TIME: O(n) build, O(1) per query | SPACE: O(n)
• CLASSIC BUG: Off-by-one in prefix indexing (pre has n+1 elements; pre[0] = 0, not a[0])
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Precompute cumulative sums to answer range queries in $O(1)$—one of the highest-value techniques per line of code in competitive programming.

Difficulty: Beginner | Prerequisites: Arrays and Strings | CF Rating: 900–1400 | Contest Frequency: Common

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Common Mistakes & Debugging
• Self-Test
• Practice Problems
• Further Reading
• Recognition and Recall
• Rating Progression
• Before You Code Checklist
• What Would You Do If...?
• Where Else This Idea Appears
• Historical Note
• What to Solve Next

---

Intuition

You have this array of six sensor readings:

  Index:  0    1    2    3    4    5
        +----+----+----+----+----+----+
  a[]:  |  3 |  1 |  4 |  1 |  5 |  9 |
        +----+----+----+----+----+----+

Your task: answer 10 queries of the form "what is the sum of elements from index $l$ to index $r$?"

Your first instinct—loop from $l$ to $r$ and add everything up. Let's watch what happens on three of those queries:

Query 1: sum of $a[1..4]$

  a[1] + a[2] + a[3] + a[4] = 1 + 4 + 1 + 5 = 11       (4 additions)

Query 2: sum of $a[0..5]$

  a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
      = 3 + 1 + 4 + 1 + 5 + 9 = 23                      (5 additions)

Query 3: sum of $a[2..4]$

  a[2] + a[3] + a[4] = 4 + 1 + 5 = 10                   (3 additions)

Three queries, 12 additions. Queries 1 and 3 both scanned indices 2, 3, 4—we added those same values twice. Every query re-walks elements that earlier queries already touched.

Scale it up: each query costs up to $O(n)$. With 10 queries on a 6-element array that is already $10\times 6=60$ operations in the worst case. On a real contest input ($n=2\times {10}^5$, $Q=2\times {10}^5$), the naive approach does up to $4\times {10}^{10}$ additions—a guaranteed TLE.

We are summing the same subsequences over and over again. There has to be a better way.

Precompute a running total of the array once; then any range sum is a single subtraction—$\text{pre}[r+1]-\text{pre}[l]$—answered in $O(1)$.

Think of an odometer in a car. You want to know the distance you drove between mile marker 2 and mile marker 5. You don't re-drive the road and count each mile—you read the odometer at both points and subtract: $14-4=10$ miles. The prefix sum array is your odometer: $\text{pre}[i]$ records the cumulative "distance" (sum) from the start of the array through the first $i$ elements.

The analogy fits well but breaks in one important place: an odometer only goes forward, and so do prefix sums. If someone changes a value in the middle of the array (an "update"), every prefix entry from that point onward becomes stale. Rebuilding costs $O(n)$, so if updates and queries are interleaved you are back to slow. Prefix sums only work on static arrays—when values change, you need a Fenwick tree or segment tree instead.

Visual Walkthrough

Same array, same queries—now solved with prefix sums.

Step 1: Build the prefix sum array

Scan left to right, accumulating a running total. We set $\text{pre}[0]=0$ as a sentinel so the query formula works cleanly even when $l=0$.

  a[]:    3    1    4    1    5    9

  pre[0] = 0
  pre[1] = pre[0] + a[0] = 0  + 3 =  3
  pre[2] = pre[1] + a[1] = 3  + 1 =  4
  pre[3] = pre[2] + a[2] = 4  + 4 =  8
  pre[4] = pre[3] + a[3] = 8  + 1 =  9
  pre[5] = pre[4] + a[4] = 9  + 5 = 14
  pre[6] = pre[5] + a[5] = 14 + 9 = 23

  Index:  0    1    2    3    4    5    6
        +----+----+----+----+----+----+----+
  pre[]:|  0 |  3 |  4 |  8 |  9 | 14 | 23 |
        +----+----+----+----+----+----+----+

Cost: 6 additions (one pass, $O(n)$). We pay this once.

Step 2: Answer Query 1—sum of $a[1..4]$

  pre[]: 0    3    4    8    9   14   23
         +----+----+----+----+----+----+----+
  index: 0    1    2    3    4    5    6
              ^                   ^
              |                   |
             l=1               r+1=5

  sum = pre[r+1] - pre[l]
      = pre[5]   - pre[1]
      = 14       - 3
      = 11  OK

Cost: 1 subtraction. Brute force needed 4 additions.

Step 3: Answer Query 2—sum of $a[0..5]$

  pre[]: 0    3    4    8    9   14   23
         +----+----+----+----+----+----+----+
  index: 0    1    2    3    4    5    6
         ^                                ^
         |                                |
        l=0                            r+1=6

  sum = pre[6] - pre[0]
      = 23     - 0
      = 23  OK

Cost: 1 subtraction. Brute force needed 5 additions. Notice how $l=0$ works smoothly thanks to the $\text{pre}[0]=0$ sentinel.

Step 4: Answer Query 3—sum of $a[2..4]$

  pre[]: 0    3    4    8    9   14   23
         +----+----+----+----+----+----+----+
  index: 0    1    2    3    4    5    6
                   ^              ^
                   |              |
                  l=2          r+1=5

  sum = pre[r+1] - pre[l]
      = pre[5]   - pre[2]
      = 14       - 4
      = 10  OK

Cost: 1 subtraction. Brute force needed 3 additions.

Operation count—head to head:

  +---------------------------------------------+
  |                Brute Force    Prefix Sums    |
  +---------------------------------------------+
  |  Build step          --        6 adds        |
  |  Query 1          4 adds      1 subtract     |
  |  Query 2          5 adds      1 subtract     |
  |  Query 3          3 adds      1 subtract     |
  +---------------------------------------------+
  |  TOTAL (3 Q)     12 ops       9 ops          |
  |  TOTAL (10 Q)    ~60 ops     16 ops          |
  +---------------------------------------------+
  |  At contest scale (n = Q = 2e5):             |
  |    Brute force:   ~4 * 10^10 ops   --> TLE   |
  |    Prefix sums:   ~4 * 10^5  ops   --> AC    |
  +---------------------------------------------+

The gap is small at 3 queries, meaningful at 10, and decisive at contest scale—a 100,000× speedup.

The Invariant

+------------------------------------------------------------------+
| INVARIANT:                                                        |
|   pre[i] = a[0] + a[1] + ... + a[i-1]   (sum of first i elems)  |
|   pre[0] = 0                              (empty prefix)         |
|                                                                   |
| RANGE SUM RULE:                                                   |
|   sum of a[l..r] = pre[r+1] - pre[l]                            |
+------------------------------------------------------------------+

Why the formula works: $\text{pre}[r+1]$ holds $a[0]+a[1]+\cdots +a[r]$, and $\text{pre}[l]$ holds $a[0]+a[1]+\cdots +a[l-1]$. Subtracting cancels the first $l$ terms, leaving exactly $a[l]+a[l+1]+\cdots +a[r]$.

Why the invariant is maintained: Each step of the build loop computes $\text{pre}[i+1]=\text{pre}[i]+a[i]$. By induction, if $\text{pre}[i]$ equals the sum of the first $i$ elements, then $\text{pre}[i+1]$ equals the sum of the first $i+1$ elements. Look at Step 1 of the walkthrough—every line follows this pattern exactly, so the invariant holds after the full pass.

The sentinel matters: Setting $\text{pre}[0]=0$ means the formula $\text{pre}[r+1]-\text{pre}[l]$ works even when $l=0$. Look at Step 3 above—the query $a[0..5]$ resolves to $\text{pre}[6]-\text{pre}[0]=23-0=23$ with no special case needed. Without the sentinel you would need an if (l == 0) branch, which is a classic source of off-by-one bugs.

What the Code Won't Teach You

Prefix sums on hash maps solve "subarray with sum = k." The classic non-obvious application: count subarrays with sum exactly $k$. Build the prefix sum array, then maintain a hash map recording how many times each prefix sum value has appeared so far. For each index $j$, ask: "has prefix[j] - k appeared before?" If it has, then some earlier index $i$ gave p[j] - p[i] = k, meaning the subarray a[i..j-1] sums to exactly $k$. The sentinel freq[0] = 1 handles subarrays that start at index 0—without it, whole-array sums equal to $k$ go uncounted.

  Array: [1, 2, -1, 3, 1],  k = 3

  Index:   0    1    2    3    4
  a[]:     1    2   -1    3    1
  p[]:  0  1    3    2    5    6
        ^
        sentinel

  Scan p[] left to right, hash map tracks seen prefix values:

  p[0]=0: freq={0:1}
  p[1]=1: need 1-3=-2, not found. freq={0:1, 1:1}
  p[2]=3: need 3-3=0, found 1 time! count=1. freq={0:1, 1:1, 3:1}
  p[3]=2: need 2-3=-1, not found. freq={0:1, 1:1, 3:1, 2:1}
  p[4]=5: need 5-3=2, found 1 time! count=2. freq={..., 5:1}
  p[5]=6: need 6-3=3, found 1 time! count=3. freq={..., 6:1}

  Answer: 3 subarrays with sum 3:
    a[0..1] = 1+2 = 3         (p[2]-p[0] = 3-0 = 3)
    a[2..4] = -1+3+1 = 3      (p[5]-p[2] = 6-3 = 3)
    a[3..3] = 3               (p[4]-p[3] = 5-2 = 3)

Prefix sums work with any operation that has an inverse. The technique generalizes to any binary operation that can be "undone": sum (inverse: subtraction), XOR (self-inverse), and multiplication over a field (inverse: division, when no zeros are present). The dealbreaker for min and max is precisely that neither has an inverse. Knowing the minimum of a[0..5] and of a[0..2] tells you nothing about the minimum of a[3..5]—there is no "unmin" operation. Use a sparse table for static range-minimum queries instead.

  Operations with inverses:           Operations WITHOUT inverses:
  +---------------------------+       +---------------------------+
  | SUM:    inverse = subtract|       | MIN:    no inverse!       |
  | XOR:    inverse = XOR     |       | MAX:    no inverse!       |
  | MULT:   inverse = divide  |       | GCD:    no inverse!       |
  |         (if no zeros)     |       |                           |
  | PREFIX SUMS WORK OK       |       | PREFIX SUMS DON'T WORK X  |
  |                           |       | Use: sparse table, seg tree|
  +---------------------------+       +---------------------------+

Offline queries + prefix sums is a powerful pattern. Some problems mix updates and queries in a way that looks inherently online—but if the problem allows reordering the queries (offline), sort them and sweep with a single prefix sum pass. The "update + query" structure collapses into a pure prefix sum problem. This is easy to miss, especially under contest pressure, but it regularly converts an $O(n\log n)$ or $O(n\sqrt{n})$ solution into $O(n)$.

Beyond these patterns, recognizing the right moment to reach for prefix sums—rather than a heavier structure—is itself a skill worth sharpening.

When to Reach for This

Trigger phrases—if you see these in a problem statement, think prefix sums:

• "Answer $Q$ range sum queries on a static array"—direct 1D prefix sums. The bread and butter.
• "Count subarrays whose sum equals $k$"—prefix sum + hash map. If $\text{pre}[j]-\text{pre}[i]=k$, the subarray $a[i..j-1]$ sums to $k$.
• "Sum over a sub-rectangle of a grid"—2D prefix sums with inclusion-exclusion.
• "Apply many range additions, then read the final array"—difference array (the inverse of prefix sums): set $d[l]+=v$, $d[r+1]-=v$, then take a prefix sum of $d$ at the end.
• "Range XOR queries on a static array"—prefix XOR. XOR is its own inverse, so $\text{xor}(l,r)=\text{px}[r+1]\oplus \text{px}[l]$, same pattern.

Counter-examples—problems that look like prefix sums but need a different tool:

• "Range sum queries with point or range updates"—once an element changes, the entire prefix array from that point onward is stale. Rebuilding costs $O(n)$ per update. Use a Fenwick tree (BIT) for point updates + range queries in $O(\log n)$, or a segment tree with lazy propagation for range updates + range queries. See: 13-binary-indexed-tree-fenwick.md, 15-segment-tree.md.
• "Find the longest subarray with sum at most $k$"—you might use prefix sums internally, but the core technique is a sliding window or two-pointer approach. Prefix sums alone give you individual range sums, not the "longest" optimality condition. See: 06-sliding-window.md.
• "Range minimum query"—subtraction does not work for min/max (there is no inverse operation for min). Use a sparse table for static RMQ in $O(1)$ per query, or a segment tree for dynamic RMQ. See: sparse-table.md.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
partial_sum(first, last, dest)	<numeric>	Writes inclusive prefix sums to dest	$O(n)$
partial_sum(first, last, dest, op)	<numeric>	Prefix fold with custom binary op	$O(n)$
inclusive_scan(first, last, dest)	<numeric>	Like partial_sum; allows parallelism (C++17)	$O(n)$
inclusive_scan(first, last, dest, op, init)	<numeric>	Inclusive scan with custom op and initial value	$O(n)$
exclusive_scan(first, last, dest, init)	<numeric>	Prefix sum excluding current element (C++17)	$O(n)$
exclusive_scan(first, last, dest, init, op)	<numeric>	Exclusive scan with custom op	$O(n)$
adjacent_difference(first, last, dest)	<numeric>	Inverse of prefix sum: computes a[i] - a[i-1]	$O(n)$
adjacent_difference(first, last, dest, op)	<numeric>	Adjacent fold with custom binary op	$O(n)$

Which to use: exclusive_scan with init=0 gives the standard 0-based prefix sum (p[i] = a[0]+...+a[i-1]), matching the convention used throughout this chapter. inclusive_scan gives the 1-based form (p[i] = a[0]+...+a[i]). partial_sum is the pre-C++17 equivalent of inclusive_scan—no parallel execution policy, otherwise identical.

---

Implementation (Contest-Ready)

Indexing Convention

This notebook uses 0-indexed prefix sums: p[0] = 0, p[i] = a[0] + a[1] + ... + a[i-1]. Sum of range [l, r] (inclusive) = p[r+1] - p[l].

The alternative 1-indexed convention (p[0] = 0, p[i] = a[1] + ... + a[i], sum [l,r] = p[r] - p[l-1]) is equally valid but mixing the two is the #1 source of off-by-one errors. Pick one and stick with it throughout a contest.

Minimal Contest Template

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

// --- 1D prefix sum ---
// p[0] = 0, p[i] = a[0] + ... + a[i-1]
// sum(l, r) = p[r+1] - p[l]  (0-indexed, inclusive both ends)
struct PrefixSum1D {
    vector<long long> p;
    PrefixSum1D() = default;
    PrefixSum1D(const vector<int>& a) : p(a.size() + 1, 0) {
        for (int i = 0; i < (int)a.size(); i++)
            p[i + 1] = p[i] + a[i];
    }
    long long query(int l, int r) const { return p[r + 1] - p[l]; }
};

// --- 2D prefix sum ---
// sum of rectangle (r1,c1) to (r2,c2), 0-indexed, inclusive
struct PrefixSum2D {
    vector<vector<long long>> p;
    PrefixSum2D() = default;
    PrefixSum2D(const vector<vector<int>>& a) {
        int R = a.size(), C = a[0].size();
        p.assign(R + 1, vector<long long>(C + 1, 0));
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                p[i + 1][j + 1] = a[i][j] + p[i][j + 1] + p[i + 1][j] - p[i][j];
    }
    long long query(int r1, int c1, int r2, int c2) const {
        return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
    }
};

// --- Difference array ---
// Supports O(1) range add, then O(n) to materialize
struct DiffArray {
    vector<long long> d;
    DiffArray(int n) : d(n + 1, 0) {}
    void add(int l, int r, long long v) { d[l] += v; d[r + 1] -= v; }
    vector<long long> build() {
        vector<long long> a(d.size() - 1);
        a[0] = d[0];
        for (int i = 1; i < (int)a.size(); i++) a[i] = a[i - 1] + d[i];
        return a;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    PrefixSum1D ps(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ps.query(l, r) << "\n";
    }
}

Annotated Version

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // --- 1D Prefix Sum ---
    // We use size n+1 so that p[0] = 0 acts as a sentinel.
    // This avoids special-casing l=0 in range queries.
    vector<long long> p(n + 1, 0);
    for (int i = 0; i < n; i++) {
        // p[i+1] stores the sum of a[0..i], so the running total
        // grows by a[i] each step.
        p[i + 1] = p[i] + a[i];
    }

    // Answer range sum queries in O(1).
    // For query [l, r] (0-indexed, inclusive):
    //   sum = p[r+1] - p[l]
    // This works because p[r+1] = a[0]+...+a[r]
    // and p[l] = a[0]+...+a[l-1], so the difference is a[l]+...+a[r].
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << p[r + 1] - p[l] << "\n";
    }

    // --- 2D Prefix Sum Example ---
    // Suppose we have an R x C grid.
    int R = 3, C = 4;
    vector<vector<int>> grid = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };

    // p2[i][j] = sum of all elements in grid[0..i-1][0..j-1].
    // Extra row and column of zeros avoids boundary checks.
    vector<vector<long long>> p2(R + 1, vector<long long>(C + 1, 0));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            // Inclusion-exclusion to build:
            // Add the cell, add prefix from above, add prefix from left,
            // subtract the overlap (top-left corner counted twice).
            p2[i + 1][j + 1] = grid[i][j]
                + p2[i][j + 1]     // top
                + p2[i + 1][j]     // left
                - p2[i][j];        // overlap
        }
    }

    // Query: sum of rectangle (r1,c1) to (r2,c2), 0-indexed inclusive.
    // Uses the same inclusion-exclusion in reverse.
    int r1 = 1, c1 = 1, r2 = 2, c2 = 3;
    long long rect_sum = p2[r2 + 1][c2 + 1]
        - p2[r1][c2 + 1]
        - p2[r2 + 1][c1]
        + p2[r1][c1];
    // rect_sum = 6+7+8+10+11+12 = 54
    cout << "Rectangle sum: " << rect_sum << "\n";

    // --- Difference Array Example ---
    // Scenario: n elements, all initially zero, with range-add updates.
    int dn = 6;
    vector<long long> d(dn + 1, 0); // size n+1 to safely write d[r+1]

    // "Add 5 to range [1, 3]"  (0-indexed inclusive)
    // Conceptually: the +5 starts at index 1, and the -5 cancels it
    // right after index 3. When we take prefix sums of d[], the +5
    // propagates across [1..3] and stops.
    d[1] += 5;
    d[3 + 1] -= 5;

    // "Add 3 to range [2, 5]"
    d[2] += 3;
    d[5 + 1] -= 3;

    // Materialize the result by taking prefix sums of d[].
    vector<long long> result(dn);
    result[0] = d[0];
    for (int i = 1; i < dn; i++) {
        result[i] = result[i - 1] + d[i];
    }
    // result = [0, 5, 8, 8, 3, 3]
    for (int i = 0; i < dn; i++) cout << result[i] << " \n"[i == dn - 1];
}

---

Operations Reference

Operation	Time	Space
Build 1D prefix sum	$O(n)$	$O(n)$
1D range sum query	$O(1)$	--
Build 2D prefix sum	$O(R\cdot C)$	$O(R\cdot C)$
2D rectangle sum query	$O(1)$	--
Difference array: single range add	$O(1)$	--
Difference array: materialize result	$O(n)$	$O(n)$
Build prefix XOR	$O(n)$	$O(n)$
XOR range query	$O(1)$	--

---

Problem Patterns & Tricks

Static Range Sum Queries

The direct application. Build once in $O(n)$, then every "sum of $a[l..r]$" query costs a single subtraction. No data structure needed—just an array of size $n+1$.

// After building p[], answer each query:
cout << p[r + 1] - p[l] << "\n";

Problems: CSES -- Static Range Sum Queries, CF 1915E

---

Subarray Sum Equals K (Prefix Sum + Hash Map)

Count subarrays with sum equal to $k$. If $p[j]-p[i]=k$, then the subarray $[i,j)$ has sum $k$. Iterate $j$, keep a hash map of how many times each prefix sum value has appeared.

long long count = 0;
unordered_map<long long, int> freq;
freq[0] = 1;
long long cur = 0;
for (int x : a) {
    cur += x;
    count += freq[cur - k];
    freq[cur]++;
}

Problems: CF 1398C, CF 1512E

---

Difference Array for Batch Range Updates

The inverse of prefix sums. When all updates arrive before any reads, encode each "add $v$ to $[l,r]$" as d[l] += v; d[r+1] -= v in $O(1)$, then take a single prefix sum at the end to materialize the result. The key condition: you can't interleave updates and reads—everything accumulates first, then resolves in one pass.

d[l] += v; d[r + 1] -= v;  // each update O(1)
// ... after all updates, prefix sum d[] to get result

Problems: CF 276C, CF 295A

---

2D Prefix Sums for Rectangle Queries

Same idea in two dimensions: precompute P[i][j] = sum of all cells in grid[0..i-1][0..j-1], then answer any sub-rectangle query in $O(1)$ via inclusion-exclusion. The build formula and query formula each use four terms. This pattern appears constantly in grid DP and computational geometry—recognizing it is worth as much as implementing it.

Problems: CF 1722E, CSES -- Forest Queries

---

Prefix XOR for Range XOR Queries

The same structural trick, with XOR instead of addition. XOR's self-inverse property ($a\oplus a=0$) plays the role that subtraction plays for sums. Build $px[i]=a[0]\oplus a[1]\oplus \cdots \oplus a[i-1]$; then $\text{xor}(l,r)=px[r+1]\oplus px[l]$ cancels the prefix exactly. Problems involving "find subarrays with XOR equal to $k$" use the prefix-XOR + hash map pattern, identical to the subarray-sum-equals-$k$ approach.

vector<int> px(n + 1, 0);
for (int i = 0; i < n; i++) px[i + 1] = px[i] ^ a[i];
// xor of a[l..r] = px[r+1] ^ px[l]

Problems: CF 1879D, CF 1848B

---

Maximum Subarray Sum (Kadane via Prefix Sum)

Any subarray sum $a[i..j]$ equals $p[j+1]-p[i]$. To maximize it, you want the largest $p[j+1]$ paired with the smallest $p[i]$ where $i\le j+1$. Track the running minimum prefix sum as you scan right; at each position the best ending subarray is p[j+1] - running_min.

long long best = LLONG_MIN, mn = 0, cur = 0;
for (int x : a) {
    cur += x;
    best = max(best, cur - mn);
    mn = min(mn, cur);
}

Problems: CF 1370C, CSES -- Maximum Subarray Sum

---

2D Difference Array for Rectangle Updates

Extend the 1D difference array idea to 2D. To add $v$ to every cell in rectangle $(r_1,c_1)$ to $(r_2,c_2)$:

d[r1][c1] += v;
d[r1][c2 + 1] -= v;
d[r2 + 1][c1] -= v;
d[r2 + 1][c2 + 1] += v;
// Then do a 2D prefix sum on d[][] to materialize.

Problems: CF 1917B, CF 635A

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|  PREFIX SUMS CHEAT SHEET                                     |
+--------------------------------------------------------------+
|  WHEN TO USE:                                                 |
|  - Range sum / XOR queries on a static array                 |
|  - Batch range-add updates (difference array)                |
|  - Subarray sum == k (prefix sum + hash map)                 |
|  - Rectangle sum queries on a grid                           |
+--------------------------------------------------------------+
|  BUILD (0-indexed, p has size n+1):                          |
|    p[0] = 0;                                                  |
|    for (int i = 0; i < n; i++) p[i+1] = p[i] + a[i];       |
+--------------------------------------------------------------+
|  QUERY [l, r] inclusive:                                      |
|    sum = p[r+1] - p[l];                                      |
+--------------------------------------------------------------+
|  DIFFERENCE ARRAY (range add v to [l,r]):                    |
|    d[l] += v;  d[r+1] -= v;                                  |
|    // prefix-sum d[] at the end                              |
+--------------------------------------------------------------+
|  STL shortcut:                                                |
|    exclusive_scan(a.begin(), a.end(), p.begin(), 0LL);       |
+--------------------------------------------------------------+
|  TIME:  Build O(n), Query O(1)                               |
|  SPACE: O(n)                                                  |
+--------------------------------------------------------------+

---

Common Mistakes & Debugging

Off-by-one in Range Queries

The single most common bug. If your prefix array is 0-indexed with p[0]=0:

• Sum of a[l..r] (inclusive) = p[r+1] - p[l].
• If you use 1-indexed arrays (a[1..n]), sum of a[l..r] = p[r] - p[l-1].
• Tip: Pick one convention and stick with it for the entire contest. The 0-indexed p[0]=0 style in this guide is safest because p has no wasted slot and the formula never needs l-1.

Integer Overflow

If $n\le 2\times {10}^5$ and $a[i]\le {10}^9$, the prefix sum can reach $2\times {10}^{14}$. Use long long. If the problem says $a[i]\le {10}^{18}$, you may need __int128 or careful modular arithmetic.

Rule of thumb: If the sum could exceed $2\times {10}^9$, use long long for the prefix array, even if the input is int.

Forgetting to Materialize the Difference Array

The difference array is a packed encoding, not the final result. Every d[l] += v; d[r+1] -= v operation just schedules an update—you must still take the prefix sum of d[] to turn those bookmarks into the actual values. Printing d[] directly gives meaningless output; the prefix-sum pass is what brings the array to life.

2D Boundary Errors

The 2D prefix array must be $(R+1)\times (C+1)$—one extra row and one extra column of zeros, serving as the 2D equivalent of the 1D sentinel. Queries at the top or left edge of the grid access p[0][...] and p[...][0], which must be 0 for the inclusion-exclusion formula to hold. Allocate the padded size before writing a single value; accessing the unpadded boundary is an out-of-bounds write waiting to happen.

Negative Numbers

Prefix sums work fine with negative numbers—there is nothing special to handle. But if you are searching for a subarray with a specific sum, remember that prefix sums are not monotone when negatives are present, so you cannot binary search on them (use a hash map instead).

Debugging Tip

When a prefix sum solution gives a wrong answer, print the prefix array on a small example and check the invariant directly: p[i+1] - p[i] must equal a[i] for every $i$. If any gap is wrong, the bug is in the build step, not the query formula. This sanity check takes 30 seconds and almost always isolates the problem immediately.

Mental Traps

Trap 1: "I know prefix sums, this problem doesn't need them."

Prefix sums rarely announce themselves. They appear as a hidden component inside problems about counting subarrays, 2D rectangle sums, XOR ranges, and batch range updates—none of which says "use prefix sums" in the problem title. If you only recognize the canonical "range sum query" framing, you'll miss the technique most of the time it applies.

  WRONG thinking:                       RIGHT thinking:
  +---------------------------+         +---------------------------+
  | "Count subarrays with     |         | "Count subarrays with     |
  |  sum = k? That's a        |         |  sum = k? If p[j]-p[i]=k  |
  |  sliding window problem." |         |  then subarray [i,j) has  |
  |                           |         |  sum k. Use prefix sums   |
  | (Only works for positive  |         |  + hash map!"             |
  |  numbers!)                |         |                           |
  +---------------------------+         | (Works for ALL numbers)   |
                                        +---------------------------+

Trap 2: "Prefix XOR is different from prefix sums."

Prefix XOR follows exactly the same structure: xor(l,r) = px[r+1] ^ px[l]. XOR's self-inverse property (a ^ a = 0) makes it work the same way subtraction works for addition. Treat it as a direct analogy.

  Addition:                             XOR:
  +---------------------------+         +---------------------------+
  | p[i] = a[0]+a[1]+...+a[i-1]|       | px[i] = a[0]^a[1]^...^a[i-1]|
  |                           |         |                           |
  | sum(l,r) = p[r+1] - p[l] |         | xor(l,r) = px[r+1] ^ px[l]|
  |            ^^^subtract^^^ |         |            ^^^XOR is its  |
  |                           |         |            own inverse^^^ |
  | Works because:            |         | Works because:            |
  | (a+b) - a = b             |         | (a^b) ^ a = b             |
  +---------------------------+         +---------------------------+

Trap 3: "I need prefix sums for range queries on a changing array."

A single update to a[i] invalidates every prefix entry from index $i$ onward. Rebuilding the prefix array after each update costs $O(n)$, so the total cost becomes $O(nQ)$—worse than the brute force you were trying to escape. Static-only is a hard constraint, not a guideline. When updates are present, reach for a Fenwick tree (BIT) for point updates or a segment tree with lazy propagation for range updates.

  Static array:                         Dynamic array:
  +---------------------------+         +---------------------------+
  | Build prefix: O(n)        |         | Build prefix: O(n)       |
  | Query: O(1)               |         | Update a[i]: O(n) REBUILD|
  | Total for Q queries: O(n+Q)|        | Total: O(n*Q)  --> TLE!  |
  |           +------+        |         |           +------+       |
  |           |  AC  |        |         |           | TLE  |       |
  |           +------+        |         |           +------+       |
  +---------------------------+         +---------------------------+
                                        USE FENWICK TREE: O(log n) per op

When Your Solution is Wrong

• WA (Wrong Answer):
  • Off-by-one: using prefix[r] - prefix[l] vs prefix[r] - prefix[l-1]. Convention matters—decide if prefix[i] means sum of first $i$ elements or sum of elements $0..i$.
  • Common formula: for 1-indexed, sum of $[l,r]$ = prefix[r] - prefix[l-1]. For 0-indexed, sum of $[l,r)$ = prefix[r] - prefix[l].
  • Integer overflow: prefix sums can reach $n\times max(a_i)$—use long long.
• Debugging tip: Print the prefix array for a small example and manually verify the range sum formula before submitting.

The Mistake That Teaches

A contestant built a prefix sum array using int for an array of $2\times {10}^5$ elements each up to ${10}^9$. The prefix values exceeded $2\times {10}^{14}$, silently overflowing 32-bit integers and producing wrong answers on large tests while small samples passed perfectly. The fix was trivial—long long—but the 20-minute debugging penalty was not. Always check: $n\times max(a_i)$—does it fit in 32 bits?

---

Self-Test

• [ ] Write the prefix sum construction and the range sum query formula from memory, using the 0-indexed convention (p[0] = 0, size $n+1$).
• [ ] Compute sum(2, 5) on an array of your choice using prefix sums—get the formula right on the first try.
• [ ] Explain why prefix sums don't work for range sum queries when the array is updated (and what data structure to use instead).
• [ ] Write the 2D prefix sum construction formula and the rectangle query formula—derive the query from inclusion-exclusion principles.
• [ ] Describe the "count subarrays with sum k" algorithm using prefix sums + hash map—state the key observation and the time complexity.
• [ ] Explain why prefix minimum/maximum does NOT work like prefix sums (hint: what's the inverse of min?).

Bug Gallery

Bug 1: Difference array—applying update in wrong direction

// Want to add +5 to all elements in [l, r]
int diff[n + 2] = {};
diff[l] += 5;
diff[r] -= 5;  // ❌ Bug

Why it's wrong: The difference array technique requires diff[r+1] -= 5, not diff[r] -= 5. The subtraction cancels the addition after position r, but placing it at r excludes the last element from the update.

Fix:

diff[l] += 5;
diff[r + 1] -= 5;  // ✅ Cancel after r, not at r

---

Bug 2: 2D prefix sum—building row and column sums independently

// Build 2D prefix sum
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        p[i][j] = p[i-1][j] + p[i][j-1] + a[i][j];  // ❌ Bug

Why it's wrong: Adding p[i-1][j] and p[i][j-1] double-counts the rectangle p[i-1][j-1]. The inclusion-exclusion principle requires subtracting it.

Fix:

p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];  // ✅

---

Bug 3: Prefix XOR range query—using subtraction instead of XOR

// Range XOR query for [l, r]
long long px[n + 1] = {};
for (int i = 1; i <= n; i++)
    px[i] = px[i-1] ^ a[i];
cout << px[r] - px[l-1] << "\n";  // ❌ Bug

Why it's wrong: XOR is its own inverse. The "cancel out" operation for prefix XOR is ^, not -. Using subtraction gives a meaningless result.

Fix:

cout << (px[r] ^ px[l-1]) << "\n";  // ✅ XOR undoes XOR

---

Bug 4: Subarray count—modifying prefix sum before checking the map

unordered_map<long long, int> cnt;
cnt[0] = 1;
long long psum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
    psum += a[i];
    cnt[psum]++;              // ❌ Bug: inserted before checking
    if (cnt.count(psum - k))
        ans += cnt[psum - k];
}

Why it's wrong: By inserting psum into the map before checking for psum - k, when k == 0 the code counts the current prefix as a valid pair with itself. The insert must happen after the check.

Fix:

psum += a[i];
if (cnt.count(psum - k))
    ans += cnt[psum - k];
cnt[psum]++;  // ✅ Insert after checking

---

Bug 5: 0/1-index confusion—querying prefix[r] - prefix[l] instead of prefix[r] - prefix[l-1]

// Query sum of a[l..r] (1-indexed)
long long query(int l, int r) {
    return prefix[r] - prefix[l];  // ❌ Bug
}

Why it's wrong: prefix[l] is the sum of elements a[1..l], so subtracting it excludes a[l] from the result. The range [l, r] should subtract prefix[l-1] to include a[l].

Fix:

return prefix[r] - prefix[l - 1];  // ✅ Include a[l] in the range

---

Bug 6: Integer overflow—using int prefix sums when element sums exceed 2^31

int a[200001], prefix[200001];
// a[i] up to 10^9, n up to 2*10^5
for (int i = 1; i <= n; i++)
    prefix[i] = prefix[i-1] + a[i];  // ❌ Bug: sum overflows int

Why it's wrong: With n = 2x10^5 elements each up to 10^9, the prefix sum can reach 2x10^{14}, which far exceeds INT_MAX ~= 2.1x10^9. The sum silently wraps around, giving wrong answers.

Fix:

long long prefix[200001] = {};
for (int i = 1; i <= n; i++)
    prefix[i] = prefix[i-1] + a[i];  // ✅ Use long long

---

Bug 7: Forgetting prefix[0] = 0—uninitialized base case

int prefix[200001];
for (int i = 1; i <= n; i++)
    prefix[i] = prefix[i-1] + a[i];
// prefix[0] never set ❌ Bug
long long ans = prefix[3] - prefix[0];  // garbage value

Why it's wrong: prefix[0] must be 0 (the sum of zero elements). Without explicit initialization, it contains garbage, corrupting all prefix values. Using int prefix[n+1] = {}; or memset is essential.

Fix:

int prefix[200001] = {};  // ✅ Zero-initialize; prefix[0] = 0 automatically
for (int i = 1; i <= n; i++)
    prefix[i] = prefix[i-1] + a[i];

Spot the Bug

Find and fix the bug in each snippet (answers in spoiler tags).

Spot Bug 1:

// 1-indexed prefix sum, query sum of a[l..r]
vector<long long> p(n + 1);
for (int i = 1; i <= n; i++)
    p[i] = p[i-1] + a[i];
cout << p[r] - p[l] << "\n";  // Bug here

Answer

Should be p[r] - p[l-1] for inclusive range [l, r]. Using p[l] excludes element a[l] from the sum.

Spot Bug 2:

// 2D prefix sum query for rectangle (r1,c1) to (r2,c2)
long long ans = p[r2][c2] - p[r1-1][c2] - p[r2][c1-1] + p[r1][c1];

Answer

The last term should be p[r1-1][c1-1], not p[r1][c1]. The inclusion-exclusion principle requires subtracting the overlap region which starts at (r1-1, c1-1).

Spot Bug 3:

// Count subarrays with sum == k
unordered_map<long long, int> cnt;
long long psum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
    psum += a[i];
    if (cnt.count(psum - k)) ans += cnt[psum - k];
    cnt[psum]++;
}

Answer

Missing initialization cnt[0] = 1. Without it, subarrays starting from index 0 whose sum equals k are not counted (when psum itself equals k, we need to find psum - k = 0 in the map).

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Static Range Sum Queries	CSES	Easy	Direct 1D prefix sum
2	CF 276C -- Little Girl and Maximum Sum	CF *1500	Easy	Difference array + sort
3	CF 1398C -- Good Subarrays	CF *1600	Medium	Prefix sum + hash map counting
4	Forest Queries	CSES	Medium	2D prefix sums
5	CF 1915E -- Romantic Glasses	CF *1300	Medium	Prefix sum + set for seen values
6	Maximum Subarray Sum	CSES	Medium	Prefix sum + running min
7	CF 1879D -- Sum of XOR Functions	CF *1700	Medium-Hard	Prefix XOR + bit contribution
8	CF 1722E -- Counting Rectangles	CF *1600	Medium	2D prefix sums on value grid
9	CF 295A -- Greg and Array	CF *1400	Medium	Nested difference arrays
10	CF 1512E -- Permutation by Sum	CF *1600	Medium	Prefix sum reasoning + greedy

---

Further Reading

• cp-algorithms—Prefix Sums—thorough treatment with 2D and 3D extensions.
• Codeforces Blog—Prefix Sums and Difference Arrays—community editorial-style overview.
• USACO Guide—Prefix Sums—well-structured with graded problems.
• For range queries with updates, see: 13-binary-indexed-tree-fenwick.md and 15-segment-tree.md.

Related topics in this notebook:

• Sliding Window—closely related; when to use which
• Binary Search—prefix sum + binary search for threshold queries
• Two Pointers—complement prefix sums for subarray problems
• Sorting and Searching—sorting + prefix sums is a common combo
• Data Structure Selection Guide—decision framework

---

Recognition and Recall

The core shift is economic: instead of paying $O(n)$ per query at query-time, you pay $O(n)$ once at build-time and collect $O(1)$ at every query thereafter. Everything else—the formula, the sentinel, the 2D extension—follows from that one commitment.

The fingerprint to burn into memory: static array + many range-sum queries → Prefix Sums. A useful mnemonic: "Build once, query forever—every range is just two bookmarks."

Rating Progression

• CF 1200: Direct 1D prefix sums for range sum queries; count subarrays with a target sum using prefix sums + hash map.
• CF 1500: 2D prefix sums with inclusion-exclusion; prefix XOR for subarray XOR queries; combine with difference arrays.
• CF 1800: Prefix sums on transformed arrays (bit decomposition, conditional sums); nested difference array + prefix sum chains.
• CF 2100: Persistent prefix sums on trees; prefix sums as building blocks inside DP transitions or convex hull trick.

Before You Code Checklist

• [ ] Confirmed the array is static (no updates between queries)—otherwise need BIT or segment tree.
• [ ] Chose 0-indexed or 1-indexed consistently and adjusted the query formula: p[r+1] - p[l] (0-indexed) or p[r] - p[l-1] (1-indexed inclusive bounds).
• [ ] For 2D prefix sums, wrote out the inclusion-exclusion formula for rectangle queries and verified signs.
• [ ] Checked for integer overflow: $n$ sums of values up to ${10}^9$ can exceed int—use long long.
• [ ] For "count subarrays with sum $k$" problems, initialized the hash map with {0: 1} to handle subarrays starting at index 0.

What Would You Do If...?

1. The array receives point updates between queries—how would you adapt from prefix sums to a data structure that supports both operations?
2. You need the minimum (not sum) over a range—why can't you subtract two "prefix minimums" the way you subtract prefix sums?
3. Your 2D prefix sum answer is off by one rectangle—how do you systematically debug the inclusion-exclusion formula?

Where Else This Idea Appears

The "precompute a running aggregate, answer range queries by subtraction" idea generalizes far beyond 1D sums:

• 2D prefix sums: Precompute P[i][j] = sum of rectangle (0,0)..(i,j). Any sub-rectangle sum is computed in $O(1)$ via inclusion-exclusion. See Forest Queries (CSES) and Counting Rectangles (CF 1722E).
• Prefix XOR: Replace addition with XOR. prefix_xor[r] ^ prefix_xor[l-1] gives the XOR of a range. Used in "find subarray with XOR = k" problems. See Sum of XOR Functions (CF 1879D).
• Prefix sums on trees (Euler-tour trick): Flatten the tree into an array via Euler tour, then apply prefix sums for subtree-sum queries. Alternatively, use root-to-node prefix sums so that path_sum(u,v) = prefix[u] + prefix[v] - 2 * prefix[lca(u,v)]. See DP on Trees.
• Sliding window and two pointers: For "longest/shortest subarray with sum >= k" on non-negative arrays, sliding window and two pointers replace or complement prefix sums.
• Segment trees and Fenwick trees: When the array is dynamic, these structures generalize the prefix-sum idea to support $O(\log n)$ updates. See the data structures chapter.

Historical Note

Prefix sums—also called cumulative sums or scan operations—trace back to early parallel computing research in the 1960s. The "parallel prefix" primitive was formally studied by Richard Ladner and Michael Fischer in 1980, who showed how to compute all prefix values of an associative operation in $O(\log n)$ time using parallel processors. The idea became foundational in hardware design (carry-lookahead adders use prefix circuits), compiler optimization, and GPU computing. Competitive programmers rediscovered the sequential version as a constant-time query trick: a simpler special case of the same structural insight.

What to Solve Next

The precompute-and-query idea doesn't stop here—it threads through every range-query structure in the book. The natural next moves:

• Difference arrays—the inverse of prefix sums, essential for batch range updates. See Difference Arrays.
• Sliding window—for "longest/shortest subarray" problems on non-negative arrays. See Sliding Window.
• Binary search on prefix sums—when prefix sums are monotone (non-negative values), binary search finds the first position where the cumulative sum exceeds a threshold. See Binary Search.
• Fenwick tree / segment tree—when the array is dynamic. See the data structures chapter.
• Practice—work through the 1100-1400 practice ladder for prefix sum drills, then Sorting and Searching for problems that combine sorting with prefix sums.
• Decision guide—see the data structure selection guide for when to pick prefix sums vs. other range-query tools.