​

Prefix Sums

​

Core Idea

prefix[0] = 0
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

sum(l, r) = prefix[r + 1] - prefix[l]

​

Complexity

​

Variations

​

1D Prefix Sum

​

2D Prefix Sum

prefix[i][j] = matrix[i-1][j-1]
             + prefix[i-1][j]
             + prefix[i][j-1]
             - prefix[i-1][j-1]

​

Prefix XOR

​

Difference Array

• Increment range [l, r] by val: diff[l] += val, diff[r+1] -= val
• Reconstruct with prefix sum

​

Classic Problems

• Range Sum Query (Immutable)
• Subarray Sum Equals K (prefix sum + hash map)
• Contiguous Array (prefix sum with transformation)
• Product of Array Except Self
• Range Sum Query 2D (Immutable)
• Count Number of Nice Subarrays

​

Pairs Well With

• Sliding Window — when window conditions involve sums
• Hash Maps — to find subarrays with a target sum in O(n)
• Binary Search — on prefix sums for threshold problems