Prefix sum is one of the most versatile techniques in competitive programming and coding interviews. It transforms O(N) range queries into O(1) lookups after O(N) preprocessing. The related difference array technique enables O(1) range updates. Together, they solve a wide class of subarray, range query, and counting problems. This guide covers the patterns, extensions to 2D, and the most common interview applications.
1D Prefix Sum
Given an array nums, the prefix sum array P is defined as: P[0] = 0, P[i] = P[i-1] + nums[i-1]. P[i] stores the sum of nums[0..i-1]. Range sum query: sum(nums[left..right]) = P[right+1] – P[left]. This is O(1) after O(N) preprocessing. Without prefix sum, each range sum query is O(N). With Q queries on an array of size N: brute force is O(N*Q); prefix sum is O(N + Q). Example: nums = [1, 2, 3, 4, 5]. P = [0, 1, 3, 6, 10, 15]. Sum of nums[1..3] = P[4] – P[1] = 10 – 1 = 9 (which is 2+3+4). Key insight: subtraction of two prefix sums gives the sum of any subarray in O(1). This is the foundation for many problems.
Subarray Sum Equals K
Count the number of contiguous subarrays whose sum equals K. Brute force: check all O(N^2) subarrays. Prefix sum + hash map: compute prefix sums as you iterate. At each position i, P[i] – K = P[j] means the subarray from j to i has sum K. Maintain a hash map counting occurrences of each prefix sum seen so far. For each P[i], check if P[i] – K exists in the map. If it does, add its count to the result. Time: O(N). Space: O(N). This pattern generalizes: subarray sum divisible by K (use prefix sum modulo K — if two prefix sums have the same modulo, the subarray between them is divisible by K), number of subarrays with sum in range [lo, hi] (count subarrays with sum <= hi minus count with sum <= lo-1), and longest subarray with sum K (store the earliest index for each prefix sum instead of the count). The hash map of prefix sums is the key technique. Whenever you see "count subarrays with sum equal to X," think prefix sum + hash map.
2D Prefix Sum
Extend prefix sums to a 2D matrix. P[i][j] = sum of all elements in the rectangle from (0,0) to (i-1,j-1). Construction: P[i][j] = P[i-1][j] + P[i][j-1] – P[i-1][j-1] + matrix[i-1][j-1]. The subtraction of P[i-1][j-1] avoids double-counting the overlap. Range sum query for rectangle (r1,c1) to (r2,c2): sum = P[r2+1][c2+1] – P[r1][c2+1] – P[r2+1][c1] + P[r1][c1]. This is the 2D inclusion-exclusion principle. O(1) per query after O(N*M) preprocessing. Applications: (1) Range Sum Query 2D (LeetCode 304) — answer multiple rectangle sum queries efficiently. (2) Maximal square/rectangle problems — combine 2D prefix sums with binary search or histogram techniques. (3) Image processing — compute the sum of pixel values in any rectangular region for blur, average filters, or feature extraction (integral images in computer vision). The 2D prefix sum is a powerful tool that appears in both coding interviews and real-world applications.
Difference Array
The difference array is the inverse of prefix sum. While prefix sum enables O(1) range queries, the difference array enables O(1) range updates. Given an array, the difference array D is: D[0] = arr[0], D[i] = arr[i] – arr[i-1]. The original array is the prefix sum of D. Range update: to add value V to all elements in range [left, right]: D[left] += V, D[right+1] -= V. After all updates, compute the prefix sum of D to get the final array. Each range update is O(1). Computing the final array is O(N). For Q updates on an array of size N: brute force is O(N*Q); difference array is O(N + Q). Applications: (1) Corporate Flight Bookings (LeetCode 1109) — add passengers to flight ranges. (2) Range addition (LeetCode 370) — multiple range additions, compute final array. (3) Car pooling — add/remove passengers at positions. Check if capacity is exceeded at any point. (4) Meeting room scheduling — add +1 at meeting start, -1 at meeting end. Prefix sum gives concurrent meetings at each time. This is a sweep line technique using the difference array principle.
Advanced Applications
Prefix sum of frequency: (1) Count of elements less than X in a range — precompute prefix sums per value (or use a Fenwick tree for dynamic updates). (2) Product of subarray — use prefix products (careful with zeros: track zero count separately). (3) XOR of subarray — prefix XOR: XOR(left..right) = prefix_xor[right+1] ^ prefix_xor[left]. Works because XOR is its own inverse. (4) Running average / moving window — prefix sum enables O(1) computation of any window average: avg(left..right) = (P[right+1] – P[left]) / (right – left + 1). Prefix sum with modular arithmetic: for problems involving divisibility, compute prefix sums modulo K. Two prefix sums with the same modulo indicate a subarray divisible by K. Count pairs with the same modulo using a hash map. This solves “count subarrays divisible by K” in O(N). Pattern recognition: if the problem involves subarray sums, range queries, range updates, or counting subarrays with a sum property, consider prefix sum or difference array. These are O(N) preprocessing techniques that reduce per-query/per-update operations to O(1).