> ## 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 ## 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. **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 * Multiple range sum queries * Finding subarray with specific sum * Equilibrium/pivot index problems * 2D matrix region sums * Running totals with modifications * 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 Sum of elements in any range Find subarrays with specific sum Where left sum equals right 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 buildPrefixSum(vector& arr) { vector 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& 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 prefix; public: NumArray(vector& 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 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& nums, int k) { // Count subarrays with sum exactly k int count = 0; int prefixSum = 0; unordered_map 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 productExceptSelf(vector& nums) { // Without division, O(1) extra space (excluding output) int n = nums.size(); vector 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> prefix; public: NumMatrix(vector>& matrix) { if (matrix.empty()) return; int m = matrix.size(), n = matrix[0].size(); prefix.assign(m + 1, vector(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 | Problem | Company | Key Concept | | --------------- | ------- | ----------------- | | Range Sum Query | All | Basic prefix sum | | Running Sum | Amazon | Simple cumulative | | Pivot Index | Meta | Left = Right sum | | 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 **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 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 ``` 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 Basic prefix sum HashMap with prefix Transform and prefix 2D prefix sum ## Practice Roadmap * Solve: Range Sum Query, Running Sum * Focus: Building and querying prefix array * Solve: Subarray Sum = K, Contiguous Array * Focus: Tracking prefix counts * Solve: 2D Range Sum Query * Focus: Inclusion-exclusion principle * Solve: Product Except Self, Maximum Subarray * Focus: Prefix products, Kadane's **Interview Tip**: When you see "sum of subarray" or "range sum query", think Prefix Sum. Add HashMap when counting subarrays with specific sum.