Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 225 · Arrays and Lists

Prefix Sums and Difference Arrays

Answer range sum queries in O(1) with prefix sums, extend to 2D grids, count subarrays with sum k using a dict, and apply range updates with difference arrays.

Suppose you have a list of daily sales and a stream of questions: "What was the total from day 10 to day 250?" Adding up 241 numbers per question is fine for one query, but with 100,000 queries on 100,000 days it takes ten billion additions. There is a classic trick that answers each question with a single subtraction.

A prefix sum array stores running totals. Once you have built it in one pass, the sum of any range is a difference of two entries. Its mirror image, the difference array, lets you add a value to a whole range of items in constant time. Together they solve a surprising number of interview problems.

The prefix sum idea

Define prefix[i] as the sum of the first i items (so prefix[0] = 0, an empty sum). Then:

TEXT
nums    =  [ 3,  1,  4,  1,  5,  9 ]
index        0   1   2   3   4   5

prefix  = [ 0,  3,  4,  8,  9, 14, 23 ]
index       0   1   2   3   4   5   6

sum of nums[2..4] (4 + 1 + 5) = prefix[5] - prefix[2] = 14 - 4 = 10

In general, the sum of nums[l..r] (both included) is prefix[r + 1] - prefix[l]. The leading 0 is what makes the formula work even when l = 0, with no special case.

Why it works: prefix[r + 1] is everything up to r, prefix[l] is everything before l. Subtracting leaves exactly l..r.

Approach Build Each query Total for q queries
Add up each range none O(n) O(n·q)
Prefix sums O(n) O(1) O(n + q)
Python Range sum queries with prefix sums

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A prefix sum array is built for data that does not change between queries. If the values are updated often, a prefix array must be rebuilt in O(n); for that case, see Fenwick trees and segment trees in Tries and Range Queries.

Equilibrium: a prefix sum in disguise

Problem. Find an index where the sum of the items on its left equals the sum on its right. With the total known, the left sum is a running total and the right sum is total - left - nums[i]. This is a prefix sum computed on the fly in O(1) space.

Python Pivot index where left sum equals right sum

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two dimensions

The same idea works for a grid. Let P[r][c] be the sum of the rectangle from the top-left corner (0, 0) up to but not including row r and column c. Build it with inclusion-exclusion:

P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]

(the top and left rectangles overlap in P[r][c], so it was counted twice). To get the sum of a rectangle with corners (r1, c1) to (r2, c2) inclusive:

P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

TEXT
 +-----+---------+
 |  A  |    B    |     wanted D = Total - (A+B) - (A+C) + A
 +-----+---------+
 |  C  |    D    |     (A is subtracted twice, so add it back once)
 +-----+---------+
Python 2D prefix sums

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Build time is O(rows × cols), each rectangle query is O(1). Draw the four regions A, B, C and D from the diagram on paper and check which ones cancel.

Subarray sum equals K

Problem. Count the contiguous subarrays whose sum equals k. The array may contain negative numbers, so a sliding window cannot be used.

Brute force. Try every start and end: O(n²) with a running sum (O(n³) if you re-add each time).

Prefix sums + dict. The subarray nums[l..r] has sum k exactly when prefix[r+1] - prefix[l] == k, i.e. prefix[l] == prefix[r+1] - k. While scanning left to right, keep a dict that counts how many times each prefix value has occurred. At each position, add counts[current - k] to the answer. One pass, O(n) time, O(n) space.

Remember to seed the dict with {0: 1}: the empty prefix lets subarrays that start at index 0 be counted.

TEXT
nums = [1, 2, 3, -3, 3],  k = 3
running   seen before (counts)         current-k   found
  1       {0:1}                          -2          0
  3       {0:1, 1:1}                      0          1   ([1,2])
  6       {0:1, 1:1, 3:1}                 3          1   ([3])
  3       {0:1, 1:1, 3:1, 6:1}            0          1   ([1,2,3,-3])
  6       {0:1, 1:1, 3:2, 6:1}            3          2   ([3,-3,3] and [3] at the end)
total = 5
Python Count subarrays with sum k

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This "remember earlier prefixes in a dict" pattern appears again in Hashing Patterns.

Difference arrays: range updates

Prefix sums answer range queries. A difference array supports range updates: "add 5 to every item from index 2 to index 6". Doing that directly costs O(length) per update. With a difference array it costs O(1), and you rebuild the final array once at the end.

Store only the changes between neighbors: diff[i] = a[i] - a[i-1]. Adding v to a[l..r] changes only two differences: diff[l] += v (the jump up) and diff[r + 1] -= v (the jump down). Taking a prefix sum of diff afterwards recovers the array.

TEXT
length 6, start all zero. add +5 to [1..3], then +2 to [2..5]
diff after both updates:  [0, +5, +2, 0, -5, 0, -2]
prefix sum of diff:       [0,  5,  7, 7,  2, 2]

Notice that diff is the inverse of a prefix sum: they undo each other.

Python Range updates with a difference array

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For u updates on an array of length n: brute force O(n·u), difference array O(n + u).

Maximum subarray sum modulo m

Given non-negative numbers and a modulus m, find the largest value of sum(subarray) % m. Kadane-style tricks fail because of the wrap-around. Use prefix sums mod m: the subarray (i, j] has sum (prefix[j] - prefix[i]) % m. For a fixed j, the best i is the smallest prefix value strictly greater than prefix[j], because then the subtraction wraps around and adds m. If no larger prefix exists, prefix[j] itself (subarray from the start) is the candidate. Keep the earlier prefix values in a sorted list and look up with bisect. That is O(n log n).

Picking random items with weights

Prefix sums also turn a weighted choice into a binary search. Build the running totals of the weights, draw a random integer below the grand total, and use bisect_right to find which bucket it falls into. Weight 6 out of 10 means 6 of the 10 possible draws land in that bucket.

Python Subarray sum mod m and weighted random picks

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Index confusion between prefix[r] and prefix[r + 1]. Write down what prefix[i] means (the sum of the first i items) and derive the formula from that.
  • Forgetting the leading zero (or the {0: 1} seed in the dict version), which loses every subarray starting at index 0.
  • Making a prefix array too short, so diff[right + 1] raises IndexError for right = n - 1.
  • Using prefix sums when the data changes between queries.
  • Integer overflow in languages with fixed-size integers. Python's ints are unbounded, but in Java or C++ use 64-bit.

Complexity summary

Technique Preprocess Query/update Space
1D prefix sum O(n) O(1) query O(n)
2D prefix sum O(rows·cols) O(1) query O(rows·cols)
Subarray sum = k (dict) none O(n) total O(n)
Difference array O(n) rebuild O(1) per update O(n)

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. With prefix[i] defined as the sum of the first i items, what is the sum of nums[l..r] (both included)?

    prefix[r + 1] covers items 0..r and prefix[l] covers items 0..l-1. The difference is l..r.
  2. 2. Why do we start the dict in subarray-sum-equals-k with {0: 1}?

    A subarray from index 0 has a prefix sum equal to k, so it needs the empty prefix (sum 0) to be seen before. Without it, those subarrays are missed.
  3. 3. Why can't a sliding window solve subarray-sum-equals-k when negative numbers are allowed?

    The window technique needs a monotonic property. With negatives, extending or shrinking the window can move the sum either way.
  4. 4. To add 7 to a[2..5] in a difference array diff, which updates do you perform?

    The value jumps up at index 2 and jumps back down just after the range ends, at index 6. A prefix sum over diff then adds 7 to exactly indexes 2 through 5.
  5. 5. You must answer 100,000 range-sum queries on a fixed array of 100,000 numbers. What is the best total cost?

    Build the prefix array in O(n), then each query is one subtraction, O(1).

Summary

  • A prefix sum array stores running totals; the sum of nums[l..r] is prefix[r + 1] - prefix[l].
  • Building costs O(n), every query O(1). It suits data that doesn't change.
  • 2D prefix sums use inclusion-exclusion for O(1) rectangle sums.
  • For "count subarrays with sum k" (negatives allowed) keep a dict of earlier prefix sums, seeded with {0: 1}.
  • A difference array turns range updates into two point updates; one prefix sum at the end rebuilds the array.

Next: Subarray Problems and Kadane's Algorithm