“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Prefix sums & difference arrays: the O(1) range query

Learn

Lesson 1 of 13 standard ~6 min

Here is the question the entire range-query family is built to dodge: you have a fixed array and you must answer "what is the sum of a[l..r]?" thousands of times. Loop each query and a thousand queries on a million-element array is 10⁹ additions — over the time limit. The fix is the oldest trick in the book: do the work once, up front.

Build a prefix array P where P[i] holds the sum of everything before index i. Then any range sum is a single subtraction.

Make it concrete. Take a = [3, 1, 4, 1, 5]. The prefix array is P = [0, 3, 4, 8, 9, 14] — one longer than a. The sum of a[1..3] is 1 + 4 + 1 = 6, and the formula gives P[4] − P[1] = 9 − 3 = 6. Build is O(n) once; every query after that is O(1).

introPredict + reveal

Using the prefix-sum identity sum(l, r) = P[r+1] − P[l], compute sum(2, 4). Work it out from the arrays below before revealing.

a = [3, 1, 4, 1, 5]          # indices 0..4
P = [0, 3, 4, 8, 9, 14]      # P[i] = sum of a[0..i-1]

sum(2, 4) = ?

Now the mirror image. What if instead of many queries you have many range updates — "add v to every element in [l, r]" — and only read the array at the end? Flip the trick: keep a difference array d, and for each update do d[l] += v and d[r+1] −= v. Each update is O(1). At the very end, take the prefix sum of d and you have the final array — every +v switches on at l and switches back off just past r.

d = [0]*(n+1)
for (l, r, v) in updates:
    d[l] += v
    d[r+1] -= v
# prefix-sum d to recover the array after all updates
for i in range(1, n):
    d[i] += d[i-1]
Range updates in O(1) each, materialized once at the end.
standardMultiple choice

You must apply many range updates of the form "add v to every a[i] for i in [l, r]" and read the array only once, at the end. Using a difference array d (1-indexed, sized n+1, all zero), what is the correct O(1) action per update?

These two are duals: prefix sums turn O(n) queries into O(1), difference arrays turn O(n) updates into O(1). They are unbeatable — until queries and updates interleave, where neither can keep up and you need a real data structure. That is the rest of this unit.