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

> Precompute cumulative sums for O(1) range queries

![Prefix Sum Pattern](https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/16-prefix-sum.svg?fit=max\&auto=format\&n=8SzFxu49daVetHjN\&q=85\&s=f1f96b50d614993d1a63bff2923dcecd)

## What is Prefix Sum?

**Prefix Sum** (cumulative sum) is a preprocessing technique that stores running totals, enabling O(1) range sum queries after O(n) preprocessing.

> [!NOTE]
>
> **Quick Recognition**: Problems involving range sums, subarray sums with target, or cumulative calculations. Keywords: "sum of range", "subarray sum equals k", "cumulative".

## Pattern Recognition Checklist

> **Use Prefix Sum When**
>
> * Multiple range sum queries
> * Finding subarray with specific sum
> * Equilibrium/pivot index problems
> * 2D matrix region sums
> * Running totals with modifications

> **Don't Use When**
>
> * Single range query (just iterate)
> * Array values change frequently (use Segment Tree)
> * Need min/max in range (use Segment Tree)
> * Need product (use prefix product)

## When to Use

> **Range Sum Queries**
>
> Sum of elements in any range

> **Subarray Sum Problems**
>
> Find subarrays with specific sum

> **Equilibrium Index**
>
> Where left sum equals right sum

> **2D Range Sum**
>
> Sum in rectangular region

## Core Concept

```python Python theme={null}
# Original array:  [1, 2, 3, 4, 5]
# Prefix sum:      [0, 1, 3, 6, 10, 15]
#                   ^ Extra 0 at start for easier indexing

# Sum of range [i, j] = prefix[j+1] - prefix[i]
# Example: sum[1:3] = prefix[4] - prefix[1] = 10 - 1 = 9

def build_prefix_sum(arr):
    prefix = [0]
    for num in arr:
        prefix.append(prefix[-1] + num)
    return prefix

def range_sum(prefix, i, j):
    """Sum of arr[i:j+1] in O(1)"""
    return prefix[j + 1] - prefix[i]
```

```java Java theme={null}
// Original array:  [1, 2, 3, 4, 5]
// Prefix sum:      [0, 1, 3, 6, 10, 15]
//                   ^ Extra 0 at start for easier indexing

// Sum of range [i, j] = prefix[j+1] - prefix[i]
// Example: sum[1:3] = prefix[4] - prefix[1] = 10 - 1 = 9

public class PrefixSum {
    public int[] buildPrefixSum(int[] arr) {
        int[] prefix = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }
    
    public int rangeSum(int[] prefix, int i, int j) {
        // Sum of arr[i:j+1] in O(1)
        return prefix[j + 1] - prefix[i];
    }
}
```

```cpp C++ theme={null}
// Original array:  [1, 2, 3, 4, 5]
// Prefix sum:      [0, 1, 3, 6, 10, 15]
//                   ^ Extra 0 at start for easier indexing

// Sum of range [i, j] = prefix[j+1] - prefix[i]
// Example: sum[1:3] = prefix[4] - prefix[1] = 10 - 1 = 9

class PrefixSum {
public:
    vector<int> buildPrefixSum(vector<int>& arr) {
        vector<int> prefix(arr.size() + 1, 0);
        for (int i = 0; i < arr.size(); i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }
    
    int rangeSum(vector<int>& prefix, int i, int j) {
        // Sum of arr[i:j+1] in O(1)
        return prefix[j + 1] - prefix[i];
    }
};
```

## Pattern Variations

### 1. Basic Range Sum

```python Python theme={null}
class NumArray:
    """Range sum query - immutable array"""
    
    def __init__(self, nums):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)
    
    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]
```

```java Java theme={null}
class NumArray {
    // Range sum query - immutable array
    private int[] prefix;
    
    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}
```

```cpp C++ theme={null}
class NumArray {
    // Range sum query - immutable array
private:
    vector<int> prefix;
    
public:
    NumArray(vector<int>& nums) {
        prefix.resize(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
};
```

### 2. Subarray Sum Equals K

```python Python theme={null}
def subarray_sum(nums, k):
    """Count subarrays with sum exactly k"""
    count = 0
    prefix_sum = 0
    prefix_count = {0: 1}  # sum to frequency
    
    for num in nums:
        prefix_sum += num
        
        # If (prefix_sum - k) exists, we found subarrays
        if prefix_sum - k in prefix_count:
            count += prefix_count[prefix_sum - k]
        
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count
```

```java Java theme={null}
public int subarraySum(int[] nums, int k) {
    // Count subarrays with sum exactly k
    int count = 0;
    int prefixSum = 0;
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1); // sum to frequency
    
    for (int num : nums) {
        prefixSum += num;
        
        // If (prefixSum - k) exists, we found subarrays
        if (prefixCount.containsKey(prefixSum - k)) {
            count += prefixCount.get(prefixSum - k);
        }
        
        prefixCount.put(prefixSum, 
            prefixCount.getOrDefault(prefixSum, 0) + 1);
    }
    
    return count;
}
```

```cpp C++ theme={null}
int subarraySum(vector<int>& nums, int k) {
    // Count subarrays with sum exactly k
    int count = 0;
    int prefixSum = 0;
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1; // sum to frequency
    
    for (int num : nums) {
        prefixSum += num;
        
        // If (prefixSum - k) exists, we found subarrays
        if (prefixCount.find(prefixSum - k) != prefixCount.end()) {
            count += prefixCount[prefixSum - k];
        }
        
        prefixCount[prefixSum]++;
    }
    
    return count;
}
```

### 3. Product of Array Except Self

```python Python theme={null}
def product_except_self(nums):
    """Without division, O(1) extra space (excluding output)"""
    n = len(nums)
    result = [1] * n
    
    # Left products
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]
    
    # Right products
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]
    
    return result
```

```java Java theme={null}
public int[] productExceptSelf(int[] nums) {
    // Without division, O(1) extra space (excluding output)
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, 1);
    
    // Left products
    int leftProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    // Right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}
```

```cpp C++ theme={null}
vector<int> productExceptSelf(vector<int>& nums) {
    // Without division, O(1) extra space (excluding output)
    int n = nums.size();
    vector<int> result(n, 1);
    
    // Left products
    int leftProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    // Right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}
```

### 4. 2D Prefix Sum (Matrix Region Sum)

```python Python theme={null}
class NumMatrix:
    """2D range sum query"""
    
    def __init__(self, matrix):
        if not matrix:
            return
        
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m):
            for j in range(n):
                self.prefix[i+1][j+1] = (matrix[i][j] 
                    + self.prefix[i][j+1] 
                    + self.prefix[i+1][j] 
                    - self.prefix[i][j])
    
    def sumRegion(self, r1, c1, r2, c2):
        return (self.prefix[r2+1][c2+1] 
            - self.prefix[r1][c2+1] 
            - self.prefix[r2+1][c1] 
            + self.prefix[r1][c1])
```

```java Java theme={null}
class NumMatrix {
    // 2D range sum query
    private int[][] prefix;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0) return;
        
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i+1][j+1] = matrix[i][j] 
                    + prefix[i][j+1] 
                    + prefix[i+1][j] 
                    - prefix[i][j];
            }
        }
    }
    
    public int sumRegion(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];
    }
}
```

```cpp C++ theme={null}
class NumMatrix {
    // 2D range sum query
private:
    vector<vector<int>> prefix;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        
        int m = matrix.size(), n = matrix[0].size();
        prefix.assign(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i+1][j+1] = matrix[i][j] 
                    + prefix[i][j+1] 
                    + prefix[i+1][j] 
                    - prefix[i][j];
            }
        }
    }
    
    int sumRegion(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];
    }
};
```

## Classic Problems

| Problem | Technique | Key Insight |
| - | - | - |
| Range Sum Query | Basic prefix | prefix\[j+1] - prefix\[i] |
| Subarray Sum K | HashMap + Prefix | Count prefix\_sum - k |
| Contiguous Array | Transform 0 to -1 | Find equal 0s and 1s |
| 2D Region Sum | 2D prefix | Inclusion-exclusion |
| Product Except Self | Left/Right prefix | Multiply both directions |

## Interview Problems by Company

**Easy**

| Problem | Company | Key Concept |
| - | - | - |
| Range Sum Query | All | Basic prefix sum |
| Running Sum | Amazon | Simple cumulative |
| Pivot Index | Meta | Left = Right sum |

**Medium**

| Problem | Company | Key Concept |
| - | - | - |
| Subarray Sum = K | Meta, Google | HashMap + prefix |
| Contiguous Array | Meta, Amazon | 0 to -1 transform |
| Product Except Self | All FAANG | Left/right prefix |
| 2D Range Sum | Google | 2D prefix grid |

## Interview Tips

> **The Key Formula**
>
> **Range sum \[i, j] = prefix\[j+1] - prefix\[i]**
>
> Why j+1? Because prefix\[k] = sum of first k elements (0 to k-1).
>
> So prefix\[j+1] = sum of elements 0 to j
> And prefix\[i] = sum of elements 0 to i-1
>
> Difference = sum of elements i to j

> **HashMap + Prefix Pattern**
>
> For "count subarrays with sum = k":
>
> ```python theme={null}
> def subarray_sum_k(nums, k):
>     prefix_count = {0: 1}  # Empty subarray has sum 0
>     prefix_sum = 0
>     count = 0
>
>     for num in nums:
>         prefix_sum += num
>         # If (prefix_sum - k) exists, we found subarrays
>         count += prefix_count.get(prefix_sum - k, 0)
>         prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
>
>     return count
> ```

> **2D Prefix Sum Formula**
>
> Build: `prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]`
>
> Query: `sum(r1,c1 to r2,c2) = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]`

## Practice Problems

> **[Range Sum Query](https://leetcode.com/problems/range-sum-query-immutable/)**
>
> Basic prefix sum

> **[Subarray Sum K](https://leetcode.com/problems/subarray-sum-equals-k/)**
>
> HashMap with prefix

> **[Contiguous Array](https://leetcode.com/problems/contiguous-array/)**
>
> Transform and prefix

> **[2D Range Sum](https://leetcode.com/problems/range-sum-query-2d-immutable/)**
>
> 2D prefix sum

## Practice Roadmap

**1. Day 1: Basic Prefix Sum**

* Solve: Range Sum Query, Running Sum
* Focus: Building and querying prefix array

**2. Day 2: HashMap + Prefix**

* Solve: Subarray Sum = K, Contiguous Array
* Focus: Tracking prefix counts

**3. Day 3: 2D Prefix Sum**

* Solve: 2D Range Sum Query
* Focus: Inclusion-exclusion principle

**4. Day 4: Variations**

* Solve: Product Except Self, Maximum Subarray
* Focus: Prefix products, Kadane's

> [!TIP]
>
> **Interview Tip**: When you see "sum of subarray" or "range sum query", think Prefix Sum. Add HashMap when counting subarrays with specific sum.


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.