Prefix Sums, Difference Arrays & O(1) Range Queries
Transform O(N) range queries into O(1) lookups. Master 1D and 2D prefix sums, subarray sum equals K with HashMaps, and difference arrays for range updates.
By the end, you’ll be able to…
- Precompute 1D Prefix Sum arrays to answer arbitrary range sum queries in O(1) time.
- Solve the 'Subarray Sum Equals K' problem in O(N) time and O(N) space using Prefix Sums paired with a HashMap.
- Apply Difference Arrays to execute multiple range increment operations in O(1) time.
01The Core Prefix Sum Technique
Imagine an array of N numbers where you need to answer Q range queries of the form: 'What is the sum of elements from index L to R?' A naive loop across L..R takes O(N) per query, resulting in O(Q * N) overall time. When Q and N are 100,000, this requires 10 billion operations, causing timeouts.
The Prefix Sum technique precomputes a cumulative running sum array in O(N) time: prefix[i] = prefix[i-1] + arr[i-1] (using 1-based indexing). To calculate the sum between any range [L, R], you simply evaluate: prefix[R + 1] - prefix[L]. The range query executes in constant O(1) time!
02Dry-Run Trace Table for Range Query
Let us trace the prefix sum precomputation and query evaluation step-by-step for the array arr = [3, 1, 4, 1, 5, 9]:
Notice how prefix[0] is initialized to 0. This dummy zero eliminates edge-case if (L == 0) checks when querying ranges starting at index 0.
+-------+-----+--------------------+-------------------------+| Index | arr | prefix computation | prefix array state |+-------+-----+--------------------+-------------------------+| - | - | prefix[0] = 0 | [0] || 0 | 3 | 0 + 3 = 3 | [0, 3] || 1 | 1 | 3 + 1 = 4 | [0, 3, 4] || 2 | 4 | 4 + 4 = 8 | [0, 3, 4, 8] || 3 | 1 | 8 + 1 = 9 | [0, 3, 4, 8, 9] || 4 | 5 | 9 + 5 = 14 | [0, 3, 4, 8, 9, 14] || 5 | 9 | 14 + 9 = 23 | [0, 3, 4, 8, 9, 14, 23] |+-------+-----+--------------------+-------------------------+Query Range [1, 4] (elements 1, 4, 1, 5 -> sum = 11):prefix[4 + 1] - prefix[1] = prefix[5] - prefix[1] = 14 - 3 = 11! Exact match in O(1)!03Subarray Sum Equals K: The Prefix Map Pattern
How do we find the total number of continuous subarrays that sum up to an arbitrary target K (including negative numbers)? A naive check of all pairs takes O(N^2) time.
By combining Prefix Sums with a HashMap, we solve this in linear O(N) time. As we iterate through the array maintaining a running prefixSum, we check if (prefixSum - K) exists in our hash map. If it exists, any subarray starting immediately after those previous prefix points and ending at the current index has a sum of exactly K.
04Why This Matters in Production
Prefix sums and difference arrays are critical for high-throughput time-series analytics, financial metrics calculation, and spatial image processing (such as 2D Integral Images for box blur filtering in computer vision).
In analytics databases, storing pre-aggregated prefix sums allows dashboard queries over historical date ranges (e.g. total revenue between March 1 and October 15) to execute in sub-microsecond O(1) time without scanning billions of individual transactional ledger rows.
05Production Architecture & Engineering Trade-Offs
Algorithmic efficiency in real-world software is heavily influenced by CPU hardware architecture, specifically the L1, L2, and L3 cache hierarchies and hardware branch predictors. While an algorithm may exhibit an optimal theoretical asymptotic complexity like O(n), poor spatial locality caused by pointer chasing across fragmented memory blocks can make it perform slower than a theoretically inferior algorithm operating over contiguous array memory.
When implementing two pointers and sliding window routines, developers must maintain strict boundary invariants to eliminate off-by-one errors and avoid redundant recomputations. Precomputing prefix sums or maintaining monotonic tracking queues transforms polynomial search operations into deterministic linear scans that execute with minimal memory allocations.
The ideas worth keeping.
- Prefix sums turn costly O(N) range queries into instant O(1) subtractions.
- Pair prefix sums with a HashMap to count subarrays with target sums in linear O(N) time.
- Difference arrays perform batch range updates in O(1) time and O(N) reconstruction time.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Range Increment via Difference Array
Given an array of zeroes of size N, write an algorithm that applies Q range additions (add value V to all elements from index L to R) in O(Q + N) time.
Explore a worked solution
public int[] applyUpdates(int n, int[][] updates) { int[] diff = new int[n + 1]; for (var u : updates) { diff[u[0]] += u[2]; diff[u[1] + 1] -= u[2]; } int[] res = new int[n]; int cur = 0; for (int i = 0; i < n; i++) { cur += diff[i]; res[i] = cur; } return res;}Difference array marks boundaries in O(1) time; running prefix sum resolves the final array in O(N) time.
Exercise 2: 2D Matrix Block Sum Query
Explain how a 2D prefix sum table calculates the sum of a subgrid bounded by (r1, c1) and (r2, c2) in O(1) time using the Principle of Inclusion-Exclusion.
Explore a worked solution
Formula: Sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1].Explanation: Subtracting the top and left rectangles removes the top-left overlapping corner twice, so adding it back restores exact balance.Inclusion-exclusion computes any 2D rectangular sum in O(1) time.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Range Increment via Difference Array
Given an array of zeroes of size N, write an algorithm that applies Q range additions (add value V to all elements from index L to R) in O(Q + N) time.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.