> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Prefix Sum & Difference Arrays

> Master range queries and updates with these fundamental techniques

# 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)**.

<Note>
  **Pattern Recognition Signal**: Whenever you see "sum of elements from index L to R" or "multiple range queries on static array", think **Prefix Sum**.
</Note>

***

## When to Use Prefix Sum

<CardGroup cols={2}>
  <Card title="Use When" icon="check">
    * Multiple range sum queries
    * Array is static (no updates)
    * Need O(1) per query after O(n) preprocessing
    * Subarray sum equals target problems
  </Card>

  <Card title="Don't Use When" icon="xmark">
    * Array has frequent updates (use Segment Tree)
    * Only one query (just iterate)
    * Need min/max in range (use Sparse Table or Segment Tree)
  </Card>
</CardGroup>

***

## 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

```cpp theme={null}
// 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.

```cpp theme={null}
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](https://codeforces.com/problemset/problem/1398/C) |
| Number of Ways | 1700   | [CF 466C](https://codeforces.com/problemset/problem/466/C)   |

***

## 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).

```cpp theme={null}
// 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.

```cpp theme={null}
// 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](https://codeforces.com/problemset/problem/816/B) |
| Greg and Array   | 1400   | [CF 295A](https://codeforces.com/problemset/problem/295/A) |

***

## Common Mistakes

<Warning>
  **Mistake 1: Integer Overflow**
  Prefix sums can grow large. Use `long long`:

  ```cpp theme={null}
  // WRONG
  vector<int> prefix(n + 1, 0);

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

<Warning>
  **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).
</Warning>

<Warning>
  **Mistake 3: Forgetting to Handle Empty Prefix**
  Initialize `prefixCount[0] = 1` for "subarray sum equals K" problems.
</Warning>

***

## Practice Problems (CP-31 & Codeforces)

### Beginner (800-1100)

| Problem                  | Concept      | Link                                                         |
| ------------------------ | ------------ | ------------------------------------------------------------ |
| Running Sum              | Basic prefix | [CF 1915A](https://codeforces.com/problemset/problem/1915/A) |
| Static Range Sum Queries | Template     | [CSES](https://cses.fi/problemset/task/1646)                 |

### Intermediate (1100-1400)

| Problem                     | Concept                | Link                                                       |
| --------------------------- | ---------------------- | ---------------------------------------------------------- |
| Little Girl and Maximum Sum | Difference array       | [CF 276C](https://codeforces.com/problemset/problem/276/C) |
| Karen and Coffee            | 2D difference          | [CF 816B](https://codeforces.com/problemset/problem/816/B) |
| Interesting drink           | Binary search + prefix | [CF 706B](https://codeforces.com/problemset/problem/706/B) |

### Advanced (1400-1700)

| Problem        | Concept                | Link                                                         |
| -------------- | ---------------------- | ------------------------------------------------------------ |
| Good Subarrays | Prefix + hashmap       | [CF 1398C](https://codeforces.com/problemset/problem/1398/C) |
| Number of Ways | Prefix sum + counting  | [CF 466C](https://codeforces.com/problemset/problem/466/C)   |
| Array Division | Binary search + prefix | [CF 808D](https://codeforces.com/problemset/problem/808/D)   |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="The Formula" icon="calculator">
    `sum(L, R) = prefix[R+1] - prefix[L]`
  </Card>

  <Card title="Use Hashmap" icon="hashtag">
    For "subarray sum = K", track prefix counts.
  </Card>

  <Card title="Difference Array" icon="arrows-left-right">
    For multiple range updates, apply at endpoints.
  </Card>

  <Card title="Watch Overflow" icon="triangle-exclamation">
    Always use `long long` for prefix sums.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 5: Two Pointers & Sliding Window" icon="arrow-right" href="/courses/competitive-programming/05-two-pointers">
  Master the art of solving subarray problems in linear time with elegant pointer techniques.
</Card>