Algorithms
Prefix Sum & Difference Array
Difficulty: Beginner
Imagine an array of a million numbers and a thousand questions of the form "what is the sum of elements between index l and r?". The naive answer loops through each query, doing roughly a billion additions in total. Prefix sums turn the...
Prefix Sum & Difference Array
Imagine an array of a million numbers and a thousand questions of the form "what is the sum of elements between index l and r?". The naive answer loops through each query, doing roughly a billion additions in total. Prefix sums turn the same workload into a million additions plus a thousand subtractions, with answers in constant time per query.
Prefix Sum & Difference Array covers the technique in three layers. You will build 1D prefix sums where prefix[i] = prefix[i-1] + arr[i] and answer any range sum in O(1). You will then learn the inverse, the difference array, which turns repeated O(n) range updates into O(1) updates that you reconstruct in a single final pass. The lesson finishes with 2D prefix sums and the inclusion-exclusion trick for answering submatrix sum queries, plus quick variants like prefix XOR and prefix product.
In Arrays & Strings, you saw why arrays support O(1) random access; that property is exactly what makes prefix lookup possible. Iteration Patterns on Arrays/Strings trained you to think in terms of single passes, and the prefix sum is the first pattern where one preprocessing pass replaces an entire family of later loops.
From here you will move into Sorting (Elementary), where rearranging the array unlocks an entirely different class of techniques.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Build a 1D prefix sum array in O(n) and answer range-sum queries in O(1).
Apply the difference array technique to perform range updates in O(1) and reconstruct the result in O(n).
Explain when to choose prefix sums versus difference arrays based on the query-update pattern.
Construct a 2D prefix sum matrix and compute submatrix sums using inclusion-exclusion.
Analyze the time and space complexity of prefix sum and difference array operations.
Why This Matters
01
Prefix sums transform repeated O(n) range-sum queries into O(1) lookups, a speedup that appears in countless problems from competitive programming to data analytics.
02
The difference array is the inverse technique: it turns repeated O(n) range-update operations into O(1) operations — essential for booking and scheduling problems.
03
Understanding prefix sums builds the foundation for advanced techniques like 2D prefix sums, prefix XOR, and Fenwick trees.
04
Prefix sum is one of the most commonly tested patterns in coding interviews because it tests whether you can preprocess data to avoid redundant computation.
Key Terms
6 terms you'll encounter in this lesson
Prefix Sum
An array where each element stores the cumulative sum of all original elements from the start up to that index. Also called a cumulative sum or running total.
Range Sum Query
A query that asks for the sum of elements between two indices [l, r]. With a prefix sum array, this is computed as prefix[r] - prefix[l-1] in O(1).
Difference Array
An array where each element stores the difference between consecutive elements of the original array. It allows O(1) range updates and O(n) reconstruction.
Inclusion-Exclusion
A counting principle used in 2D prefix sums: to avoid double-counting overlapping regions, you add and subtract sub-regions appropriately.
Prefix XOR
A variation of prefix sum using XOR instead of addition. Useful for range-XOR queries, following the same O(1) query pattern.
Preprocessing
A one-time computation (here, building the prefix sum array) that speeds up all subsequent queries. The cost is amortized over many queries.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"prefix[r] - prefix[l] gives the sum from l to r"
You need prefix[r] - prefix[l - 1], not prefix[r] - prefix[l]. Subtracting prefix[l] excludes arr[l] itself. Using a 0-indexed prefix array with a leading zero (prefix[0] = 0, prefix[i] = prefix[i-1] + arr[i-1]) avoids this off-by-one entirely.
"Prefix sums are only useful for sum queries"
The same idea applies to prefix XOR, prefix product (with caveats for zeros), and prefix min/max (though min/max prefix queries require different reconstruction formulas). The core insight — precompute cumulative results to answer range queries in O(1) — is general.
"A difference array uses more space than just modifying the original array"
Both use O(n) space. The advantage of a difference array is not space savings — it is that each range update takes O(1) instead of O(r - l + 1). After all updates, you reconstruct the array in a single O(n) pass.
"You always need a prefix sum array for range sum queries"
If you only have a few queries, a direct loop sum may be simpler and fast enough. Prefix sums shine when you have many queries (Q >> 1) on the same data, amortizing the O(n) build cost across O(Q) queries.