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).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does prefix sum enable O(1) range sum queries?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Prefix sum array P[i] stores the sum of elements from index 0 to i-1: P[0]=0, P[i]=P[i-1]+nums[i-1]. Range sum of nums[left..right] = P[right+1] – P[left]. This is O(1) after O(N) preprocessing. 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). Without prefix sum, each range query scans O(N) elements. With Q queries: brute force is O(N*Q), prefix sum is O(N+Q). Key insight: the difference of two prefix sums equals the sum of any contiguous subarray. This is the foundation for many subarray problems.”}},{“@type”:”Question”,”name”:”How do you count subarrays with sum equal to K using prefix sums?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use prefix sum + hash map. As you compute prefix sums left to right, maintain a hash map counting occurrences of each prefix sum seen so far. At position i with prefix sum P[i]: if P[i]-K exists in the map with count C, then C subarrays ending at i have sum K (because P[i]-P[j]=K means the subarray j..i sums to K). Add P[i] to the map. Initialize map with {0: 1} (empty prefix). Time: O(N). Space: O(N). This pattern generalizes: subarrays divisible by K (use prefix sum mod K — same mod means divisible subarray), longest subarray with sum K (store earliest index per prefix sum instead of count), and subarray sum in range [lo,hi] (count sum<=hi minus count sum<=lo-1). Whenever you see count subarrays with sum property, think prefix sum + hash map."}},{"@type":"Question","name":"What is a difference array and when do you use it?","acceptedAnswer":{"@type":"Answer","text":"Difference array is the inverse of prefix sum. While prefix sum enables O(1) range queries, difference array enables O(1) range updates. Difference array D: D[0]=arr[0], D[i]=arr[i]-arr[i-1]. The original array is the prefix sum of D. To add value V to range [left,right]: D[left]+=V, D[right+1]-=V. Two O(1) operations instead of updating every element in the range. After all updates, compute prefix sum of D to get the final array. For Q updates on array of size N: brute force O(N*Q), difference array O(N+Q). Applications: flight bookings (add passengers to ranges), car pooling (add/remove passengers at positions, check capacity), meeting room counting (add +1 at start, -1 at end, prefix sum gives concurrent count at each time). The sweep line technique is essentially a difference array applied to events on a timeline."}},{"@type":"Question","name":"How does 2D prefix sum work for matrix range queries?","acceptedAnswer":{"@type":"Answer","text":"Extend prefix sums to 2D: P[i][j] = sum of all elements in rectangle (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 prevents double-counting the overlap region. 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: Range Sum Query 2D (LeetCode 304), maximal square/rectangle problems, and image processing (integral images for blur/average filters). The 2D extension is conceptually simple: just apply inclusion-exclusion at each step. Draw the rectangles on paper to verify the formula signs."}}]}