Prefix Sum & Difference Arrays

The Mental Model

Imagine you’re a cashier and need to tell customers their subtotal at any point during shopping. Instead of adding items from scratch each time, you keep a running total. That’s prefix sum—precompute cumulative sums so range queries become O(1).

Pattern Recognition Signal: Whenever you see “sum of elements from index L to R” or “multiple range queries on static array”, think Prefix Sum.

When to Use Prefix Sum

Use When

Multiple range sum queries
Array is static (no updates)
Need O(1) per query after O(n) preprocessing
Subarray sum equals target problems

Don't Use When

Array has frequent updates (use Segment Tree)
Only one query (just iterate)
Need min/max in range (use Sparse Table or Segment Tree)

The Core Idea

Building Prefix Sum Array

Original:  [3, 1, 4, 1, 5, 9, 2, 6]
Prefix:    [0, 3, 4, 8, 9, 14, 23, 25, 31]
            ^-- We add a 0 at the start for easier math

Key Insight: sum(L, R) = prefix[R+1] - prefix[L] Why? Because prefix[R+1] contains sum of elements 0 to R, and prefix[L] contains sum of elements 0 to L-1. Subtracting gives us exactly L to R.

Implementation Template

// Build prefix sum array
vector<long long> buildPrefix(const vector<int>& arr) {
    int n = arr.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

// Query sum from index L to R (0-indexed, inclusive)
long long rangeSum(const vector<long long>& prefix, int L, int R) {
    return prefix[R + 1] - prefix[L];
}

// Usage
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
auto prefix = buildPrefix(arr);
cout << rangeSum(prefix, 2, 5);  // sum of arr[2..5] = 4+1+5+9 = 19

Pattern 1: Subarray Sum Equals K

Problem: Count subarrays with sum equal to K. Identification Signals:

“Count subarrays” or “find subarray”
“Sum equals K”
Constraints allow O(n) solution

The Insight: If prefix[j] - prefix[i] = K, then subarray (i, j] has sum K. Rearranging: prefix[i] = prefix[j] - K. Use a hashmap to count prefix sums seen so far.

int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> prefixCount;
    prefixCount[0] = 1;  // Empty prefix has sum 0
    
    long long currentSum = 0;
    int count = 0;
    
    for (int num : nums) {
        currentSum += num;
        
        // How many prefixes have sum = currentSum - k?
        if (prefixCount.count(currentSum - k)) {
            count += prefixCount[currentSum - k];
        }
        
        prefixCount[currentSum]++;
    }
    
    return count;
}

Codeforces Problems:

Problem	Rating	Link
Good Subarrays	1600	CF 1398C
Number of Ways	1700	CF 466C

Pattern 2: 2D Prefix Sum

Problem: Answer multiple rectangle sum queries on a 2D grid. The Insight: Build a 2D prefix sum where prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i-1, j-1).

// Build 2D prefix sum
vector<vector<long long>> build2DPrefix(const vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<long long>> prefix(n + 1, vector<long long>(m + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefix[i][j] = grid[i-1][j-1] 
                         + prefix[i-1][j] 
                         + prefix[i][j-1] 
                         - prefix[i-1][j-1];
        }
    }
    return prefix;
}

// Query sum of rectangle from (r1,c1) to (r2,c2) inclusive
long long rectSum(const vector<vector<long long>>& prefix, 
                  int r1, int c1, int r2, int c2) {
    return prefix[r2+1][c2+1] 
         - prefix[r1][c2+1] 
         - prefix[r2+1][c1] 
         + prefix[r1][c1];
}

Visual: To get the sum of the green rectangle, we use inclusion-exclusion:

+---+---+---+
| A | B |   |
+---+---+---+
| C | G |   |  G = Total - A - B - C + overlap
+---+---+---+

Pattern 3: Difference Array (Range Updates)

Problem: Apply multiple range updates, then query final array. Identification Signals:

“Add value to range [L, R]” multiple times
Query final values after all updates
No queries between updates

The Insight: Instead of updating each element, mark the start and end of changes. Then prefix sum reconstructs the array.

// Apply updates: add 'val' to range [L, R]
void rangeUpdate(vector<long long>& diff, int L, int R, long long val) {
    diff[L] += val;
    if (R + 1 < diff.size()) {
        diff[R + 1] -= val;
    }
}

// Reconstruct array from difference array
vector<long long> reconstruct(const vector<long long>& diff) {
    vector<long long> arr(diff.size());
    arr[0] = diff[0];
    for (int i = 1; i < diff.size(); i++) {
        arr[i] = arr[i-1] + diff[i];
    }
    return arr;
}

// Usage
int n = 5;
vector<long long> diff(n, 0);
rangeUpdate(diff, 1, 3, 5);  // Add 5 to indices 1-3
rangeUpdate(diff, 2, 4, 3);  // Add 3 to indices 2-4
auto result = reconstruct(diff);
// result = [0, 5, 8, 8, 3]

Codeforces Problems:

Problem	Rating	Link
Karen and Coffee	1400	CF 816B
Greg and Array	1400	CF 295A

Common Mistakes

Mistake 1: Integer Overflow Prefix sums can grow large. Use long long:

// WRONG
vector<int> prefix(n + 1, 0);

// CORRECT
vector<long long> prefix(n + 1, 0);

Mistake 2: Off-by-One Errors Remember: sum(L, R) = prefix[R+1] - prefix[L] (not prefix[R] - prefix[L-1] with 1-indexed arrays, unless you adjust).

Mistake 3: Forgetting to Handle Empty Prefix Initialize prefixCount[0] = 1 for “subarray sum equals K” problems.

Practice Problems (CP-31 & Codeforces)

Beginner (800-1100)

Problem	Concept	Link
Running Sum	Basic prefix	CF 1915A
Static Range Sum Queries	Template	CSES

Intermediate (1100-1400)

Problem	Concept	Link
Little Girl and Maximum Sum	Difference array	CF 276C
Karen and Coffee	2D difference	CF 816B
Interesting drink	Binary search + prefix	CF 706B

Advanced (1400-1700)

Problem	Concept	Link
Good Subarrays	Prefix + hashmap	CF 1398C
Number of Ways	Prefix sum + counting	CF 466C
Array Division	Binary search + prefix	CF 808D

Key Takeaways

The Formula

sum(L, R) = prefix[R+1] - prefix[L]

Use Hashmap

For “subarray sum = K”, track prefix counts.

Difference Array

For multiple range updates, apply at endpoints.

Watch Overflow

Always use long long for prefix sums.

Next Up

Chapter 5: Two Pointers & Sliding Window

Master the art of solving subarray problems in linear time with elegant pointer techniques.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Prefix Sum & Difference Arrays

Prefix Sum & Difference Arrays

The Mental Model

When to Use Prefix Sum

Use When

Don't Use When

The Core Idea

Building Prefix Sum Array

Implementation Template

Pattern 1: Subarray Sum Equals K

Pattern 2: 2D Prefix Sum

Pattern 3: Difference Array (Range Updates)

Common Mistakes

Practice Problems (CP-31 & Codeforces)

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

The Formula

Use Hashmap

Difference Array

Watch Overflow

Next Up

Chapter 5: Two Pointers & Sliding Window

​Prefix Sum & Difference Arrays

​The Mental Model

​When to Use Prefix Sum

Use When

Don't Use When

​The Core Idea

​Building Prefix Sum Array

​Implementation Template

​Pattern 1: Subarray Sum Equals K

​Pattern 2: 2D Prefix Sum

​Pattern 3: Difference Array (Range Updates)

​Common Mistakes

​Practice Problems (CP-31 & Codeforces)

​Beginner (800-1100)

​Intermediate (1100-1400)

​Advanced (1400-1700)

​Key Takeaways

The Formula

Use Hashmap

Difference Array

Watch Overflow

​Next Up

Chapter 5: Two Pointers & Sliding Window

Prefix Sum & Difference Arrays

The Mental Model

When to Use Prefix Sum

The Core Idea

Building Prefix Sum Array

Implementation Template

Pattern 1: Subarray Sum Equals K

Pattern 2: 2D Prefix Sum

Pattern 3: Difference Array (Range Updates)

Common Mistakes

Practice Problems (CP-31 & Codeforces)

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Next Up