Prefix Sum

What you'll learn

• What Is It?

  A prefix sum array is a preprocessed array where each element at index i stores the sum of all elements from the start of the original array up to index i. This transforms range-sum queries from O(n) to O(1). Core idea: Precompute cumula…

• Building the Prefix Sum Array

  Example: ---

• Range Sum Query

  Problem: Given multiple queries, each asking for the sum of elements in range [L, R]. Why it works: Complexity: O(n) build + O(1) per query vs O(n) per query without prefix sum. ---

• Alternative: Size n+1 Prefix Array (0-indexed with sentinel)

  A common variant uses an extra element at index 0 as a sentinel (prefix[0] = 0), which eliminates the L == 0 edge case: ---

• Pattern 1: Subarray Sum Equals Target

  Problem: Find if any contiguous subarray sums to a target value. Key insight: If prefix[j] - prefix[i] == target, then subarray (i, j] sums to target. Use a hash set to check in O(1). Variant - Count subarrays with sum k: Time: O(n), Spa…

• Pattern 2: Maximum Sum Subarray of Fixed Length k

  Note: This is equivalent to sliding window for fixed-size windows, but prefix sum generalizes better to variable-size queries. ---

• Pattern 3: Equilibrium Index

  Problem: Find an index where the sum of elements on the left equals the sum on the right. ---

• Pattern 4: Difference Array (Range Update in O(1))

  Problem: Apply multiple "add value to range [L, R]" operations efficiently. Key insight: Instead of updating every element in the range, mark only the start and end+1 positions: Complexity: O(1) per update, O(n) to reconstruct. Without d…

• Pattern 5: 2D Prefix Sum (Matrix Region Sum)

  Problem: Answer sum queries over rectangular subregions of a matrix. Build: Query (sum of rectangle from (r1,c1) to (r2,c2)): Inclusion-exclusion principle: ---

• Pattern 6: XOR Prefix (Range XOR Queries)

  Same principle applies to XOR since XOR is associative and self-inverse (a ^ a = 0): ---

• When to Use Prefix Sum

  | Signal | Approach | |--------|----------| | "Sum/count in range [L, R]" with many queries | Standard prefix sum | | "Subarray with sum k" or "count subarrays with sum k" | Prefix sum + hash map | | "Add value to range [L, R]" many time…

• Complexity Summary

  | Operation | Prefix Sum | Naive | |-----------|-----------|-------| | Build | O(n) | - | | Range query | O(1) | O(n) | | Point update | O(n) rebuild | O(1) | | Range update | O(1) with diff array | O(n) | Limitation: If the array is upd…