Prefix Sum and Difference Arrays

Prefix sums and difference arrays are the preprocessing tricks that make range queries and range updates cheap. They trade a one-time O(n) build for O(1) per query or update — a classic space-for-time and preprocess-for-query bargain that appears constantly.

The core idea

• Prefix sum: pre[i] = arr[0]+...+arr[i-1]. Then the sum of range [l, r] = pre[r+1] − pre[l] in O(1). Build once in O(n).
• Difference array (the inverse): to add val to every element in [l, r] many times, do diff[l] += val and diff[r+1] −= val in O(1); one prefix-sum pass at the end reconstructs the final array. Turns q range-updates from O(n·q) into O(n + q).
• 2D prefix sum: submatrix sums in O(1) via inclusion-exclusion.

Technique	Build	Query/Update	Space
1D prefix sum	O(n)	O(1) range sum	O(n)
Difference array	O(n) at end	O(1) range add	O(n)
2D prefix sum	O(mn)	O(1) submatrix	O(mn)
Prefix + hashmap	O(n)	O(n) subarray-sum-k	O(n)

Exam Tricks & Tips

• 🎯 Many static range-sum queries → build a prefix array once, answer each in O(1).
• 🎯 "Subarray sum equals k" → prefix sum + hash map of seen prefixes → O(n).
• 🎯 Range-add updates then one final read → difference array beats naive looping.
• 🎯 Use size n+1 and 1-based prefix so pre[r+1] − pre[l] is index-clean.
• 🎯 2D: pre[i][j] = a[i][j] + pre[i-1][j] + pre[i][j-1] − pre[i-1][j-1].
• ❌ Common mistake: mixing inclusive/exclusive bounds — pin down whether pre[i] includes index i before coding.

Expected pattern

Repeated range-sum queries, "count subarrays with sum k", equilibrium/pivot index, or many interval increments followed by a final snapshot. The interviewer checks that you preprocess instead of recomputing per query.

Quick recap

Prefix sum: O(n) build → O(1) range sums; pair with a hash map for subarray-sum-k in O(n). Difference array: O(1) range adds, reconstruct with one pass. Extend both to 2D via inclusion-exclusion.

Cover the answer, recall, then check. 11 cards on prefix sums and difference arrays.

Q1. Formula for the sum of range [l, r] using a prefix array?
A1. pre[r+1] − pre[l], where pre[i] = sum of the first i elements. O(1) per query.

Q2. Build cost and query cost of a prefix-sum array?
A2. O(n) build once, O(1) per range-sum query.

Q3. What does a difference array optimise?
A3. Many range-add updates: diff[l]+=v, diff[r+1]−=v in O(1) each; one prefix pass reconstructs the array.

Q4. q range-add updates on n elements — naive vs difference array?
A4. Naive O(n·q); difference array O(n + q).

Q5. "Count subarrays with sum = k" — optimal approach?
A5. Prefix sum + hash map counting seen prefix sums; add map[prefix − k] each step. O(n).

Q6. Why store prefix sums in a size n+1 array?
A6. So pre[0]=0 anchors the empty prefix, making pre[r+1] − pre[l] clean with no special-casing.

Q7. 2D prefix sum recurrence?
A7. pre[i][j] = a[i][j] + pre[i-1][j] + pre[i][j-1] − pre[i-1][j-1].

Q8. Submatrix sum from a 2D prefix array — cost?
A8. O(1) via inclusion-exclusion of four corner values.

Q9. Space complexity of prefix sum?
A9. O(n) (or O(mn) for 2D) — memory traded for O(1) queries.

Q10. Equilibrium/pivot index — how do prefix sums help?
A10. left = pre[i], right = total − pre[i] − arr[i]; pivot where left == right, in O(n).

Q11. Most common prefix-sum bug?
A11. Off-by-one from inclusive/exclusive confusion — decide whether pre[i] includes index i before writing the query.

Prefix sums answer "sum of a range" in O(1) after O(n) setup, and their mirror image — the difference array — applies many range updates in O(1) each. Together they turn repeated range work from O(n) per query into constant time.

Core idea: precompute cumulative totals once so any range aggregate becomes a single subtraction. The difference array does the reverse: record only changes, then integrate at the end.

How it works

Beginner — the prefix-sum array

Define P[0] = 0 and P[i] = a[0] + … + a[i-1]. Then the sum of a[l..r] (inclusive) is:

rangeSum(l, r) = P[r+1] - P[l]

Building P is O(n); every range-sum query is then O(1). With Q queries, brute force is O(n·Q); prefix sums make it O(n + Q).

Intermediate — the range-sum-equals-K trick

Combine prefix sums with a hash map to count subarrays summing to K in one pass. A subarray a[l..r] sums to K exactly when P[r+1] − P[l] = K, i.e. P[l] = P[r+1] − K. Store how many times each prefix value has occurred:

count = 0; seen = {0: 1}; run = 0
for x in a:
    run += x
    count += seen.get(run - K, 0)
    seen[run] = seen.get(run, 0) + 1

O(n) time, O(n) space — and it works with negative numbers, where sliding windows fail.

Advanced — the difference array for range updates

To add v to every element in [l, r] many times, don't touch the range each time. Keep diff, do diff[l] += v; diff[r+1] -= v (O(1) per update). After all updates, the prefix sum of diff reconstructs the final array in O(n). So m range updates cost O(m + n) instead of O(m·n). This is the 1-D version of what 2-D summed-area tables do for grids.

Worked example

Array [2, 4, 1, 3], find sum of indices 1..3. P = [0, 2, 6, 7, 10]. rangeSum(1,3) = P[4] − P[1] = 10 − 2 = 8 (= 4+1+3). One subtraction, no loop.

When to use it

• Prefix sum: many range-sum/average queries, "subarray sum equals K", counting problems, 2-D region sums (summed-area tables).
• Difference array: many overlapping range increments (flight bookings, interval stabbing, "add to all elements in range").

Tricks & gotchas

• Size P as n+1 and index carefully — the P[l] vs P[l−1] off-by-one is the classic bug.
• Seed the hash map with {0: 1} so subarrays starting at index 0 are counted.
• For 2-D: sum = P[r2][c2] − P[r1-1][c2] − P[r2][c1-1] + P[r1-1][c1-1] (inclusion–exclusion).
• Mnemonic: "Prefix to read ranges, difference to write ranges."

Key formulas

• Prefix sum: P[0]=a[0], P[i]=P[i−1]+a[i]; range sum a[l..r] = P[r] − P[l−1].
• Build O(n), each range-sum query O(1).
• Difference array d[l] += v, d[r+1] −= v applies +v to a[l..r] in O(1); prefix-sum d to recover the array.
• 2D prefix sum: S[i][j] = a[i][j] + S[i−1][j] + S[i][j−1] − S[i−1][j−1]; submatrix sum in O(1).
• Space O(n) (or O(mn) for 2D).

Usage: precompute prefix sums when many range-sum queries hit a static array.

Worked Example

Problem: Using a prefix-sum array, find the sum of elements from index 1 to 3 (inclusive) in arr = [2, 4, 1, 3, 5].

Solution: Build the prefix array P where P[i] = sum of arr[0..i]:

• P[0] = 2
• P[1] = 2 + 4 = 6
• P[2] = 6 + 1 = 7
• P[3] = 7 + 3 = 10
• P[4] = 10 + 5 = 15

So P = [2, 6, 7, 10, 15].

The sum of a range [L, R] is P[R] − P[L−1]. For L = 1, R = 3:
sum = P[3] − P[0] = 10 − 2 = 8.

Check directly: arr[1] + arr[2] + arr[3] = 4 + 1 + 3 = 8. ✓

Building P is O(n) once; each range query is then O(1).

Answer: The range sum is 8.