Skip to main content

​
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:
ProblemRatingLink
Good Subarrays1600CF 1398C
Number of Ways1700CF 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:
ProblemRatingLink
Karen and Coffee1400CF 816B
Greg and Array1400CF 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)

ProblemConceptLink
Running SumBasic prefixCF 1915A
Static Range Sum QueriesTemplateCSES

​
Intermediate (1100-1400)

ProblemConceptLink
Little Girl and Maximum SumDifference arrayCF 276C
Karen and Coffee2D differenceCF 816B
Interesting drinkBinary search + prefixCF 706B

​
Advanced (1400-1700)

ProblemConceptLink
Good SubarraysPrefix + hashmapCF 1398C
Number of WaysPrefix sum + countingCF 466C
Array DivisionBinary search + prefixCF 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.