Skip to content
Hari KharelStudy

Prefix sums and difference arrays

coreCommon atGoogleMetaAmazonStripeRead firstArraysComplexity analysisPractise in the Sandbox →

A prefix array stores P[k] = xs[0] + … + xs[k-1], built in one O(n) pass. Then the sum of any range xs[i..j] is P[j+1] − P[i], O(1) per query. A difference array is the reverse trick: each “add d to [lo..hi]” becomes two writes, and one prefix-sum pass at the end rebuilds the values.

The idea in plain words

Section titled “The idea in plain words”

Think of a car’s odometer. To know how far you drove between Tuesday and Friday, you don’t re-add every trip. You read the odometer on Friday night and subtract Tuesday morning’s reading.

A prefix array is that odometer for a list. P[k] is “total distance before index k”. Any stretch is one reading minus another:

  • P[j+1] covers everything up to and including j.
  • P[i] covers everything before i.
  • Their difference is exactly xs[i] + … + xs[j].

The difference array runs the idea backwards. Instead of many reads, you have many range writes (“add 5 to every seat in rows 3 to 40”). Write +5 where the effect starts and −5 just after it ends. A running total over those markers switches each effect on and off at the right places.

See it

Section titled “See it”

Step through the build, then click any two cells in the second panel. However long the range, the query is one subtraction.

Build the prefix array
step through
xs
3
-1
4
1
5
9
-2
6
01234567
P (length n + 1)
0
·
·
·
·
·
·
·
·
012345678
being writtenreused prefixalready summed
P[0] = 0: the sum of the empty prefix. That spare slot means no special case for ranges that start at index 0.
1 / 10
Query any range in O(1)
click two cells
xs: click a start, then an end
01234567
P
P[2]
0
3
2
6
7
12
21
19
25
012345678
P[6]
range[2..5]
P[j+1]21
P[i]2
sum19
brute adds4
prefix ops1
sum(xs[2..5]) = P[6] − P[2] = 21 − 2 = 19. P[6] holds everything up to index 5; subtracting P[2] cancels everything before index 2.
queried rangeP[j+1]: up to jP[i]: before i (subtract)

When to reach for it

Section titled “When to reach for it”
The problem says… Why prefix sums fit
“sum (or count) over range [i, j]”, many queries, array doesn’t change O(n) once, then O(1) per query instead of O(n).
“how many elements in [i, j] satisfy X” Prefix-sum a 0/1 indicator array.
“sum of a sub-rectangle”, repeated on a grid 2-D prefix sums (a summed-area table).
“add v to every element in [lo, hi]”, many updates, read at the end Difference array: O(1) per update, O(n) to rebuild.
“subarray whose sum equals k”, values can be negative Prefix sums turn “range sum” into “difference of two prefixes”, which a hash map can look up.
“how many intervals cover point x” (bookings, shifts, ranges on a line) +1 at each start, −1 after each end, then prefix-sum.

How it works

Section titled “How it works”

1-D prefix sums

Section titled “1-D prefix sums”
  1. Allocate P with n + 1 slots and P[0] = 0. For each k, set P[k+1] = P[k] + xs[k].
  2. Answer sum(xs[i..j]) as P[j+1] − P[i].
range_sum.py
def build_prefix(xs: list[int]) -> list[int]:
    """p[i] = sum of xs[0..i-1]. One extra slot so p[0] = 0 (the empty prefix)."""
    p = [0] * (len(xs) + 1)
    for i, x in enumerate(xs):
        p[i + 1] = p[i] + x          # 1. each prefix extends the previous one
    return p




def range_sum(p: list[int], i: int, j: int) -> int:
    """Sum of xs[i..j] inclusive, in O(1)."""
    return p[j + 1] - p[i]           # 2. everything up to j, minus everything before i




if __name__ == "__main__":
    xs = [3, -1, 4, 1, 5, 9, -2, 6]
    p = build_prefix(xs)
    assert p == [0, 3, 2, 6, 7, 12, 21, 19, 25]
    assert range_sum(p, 2, 5) == 4 + 1 + 5 + 9
    assert range_sum(p, 0, 7) == sum(xs)
    assert range_sum(p, 3, 3) == 1   # a single element
    # Brute-force cross-check on every range.
    for i in range(len(xs)):
        for j in range(i, len(xs)):
            assert range_sum(p, i, j) == sum(xs[i : j + 1])
    print("ok")

2-D prefix sums

Section titled “2-D prefix sums”

Same idea on a grid. S[r][c] is the sum of the rectangle from the top-left corner down to (but not including) row r and column c. Building and querying both use inclusion-exclusion: add the two overlapping strips, then fix the corner you counted twice.

  1. S[r+1][c+1] = grid[r][c] + S[r][c+1] + S[r+1][c] − S[r][c].
  2. sum(r1..r2, c1..c2) = S[r2+1][c2+1] − S[r1][c2+1] − S[r2+1][c1] + S[r1][c1].
grid_sum.py
def build_2d(grid: list[list[int]]) -> list[list[int]]:
    """s[r][c] = sum of the rectangle grid[0..r-1][0..c-1] (a summed-area table)."""
    rows, cols = len(grid), len(grid[0]) if grid else 0
    s = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            # 1. cell + area above + area left - overlap (counted twice)
            s[r + 1][c + 1] = grid[r][c] + s[r][c + 1] + s[r + 1][c] - s[r][c]
    return s




def rect_sum(s: list[list[int]], r1: int, c1: int, r2: int, c2: int) -> int:
    """Sum of grid[r1..r2][c1..c2] inclusive, in O(1)."""
    # 2. big rectangle - strip above - strip left + corner (subtracted twice)
    return s[r2 + 1][c2 + 1] - s[r1][c2 + 1] - s[r2 + 1][c1] + s[r1][c1]




if __name__ == "__main__":
    grid = [
        [3, 0, 1, 4],
        [5, 6, 3, 2],
        [1, 2, 0, 1],
    ]
    s = build_2d(grid)
    assert rect_sum(s, 0, 0, 2, 3) == 28           # whole grid
    assert rect_sum(s, 1, 1, 2, 2) == 6 + 3 + 2 + 0
    assert rect_sum(s, 2, 3, 2, 3) == 1            # one cell
    print("ok")

Difference arrays

Section titled “Difference arrays”

Use this when updates come first and reads come after (“offline” updates).

  1. For each update (lo, hi, d): diff[lo] += d. The effect switches on at lo.
  2. And diff[hi + 1] −= d. It switches off just after hi. Size diff as n + 1 so hi + 1 is always in bounds.
  3. Rebuild with one running sum: value[i] = diff[0] + … + diff[i].
apply_range_adds.py
def apply_range_adds(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """Start from n zeros; each (lo, hi, delta) adds delta to every index in [lo..hi].
    O(n + k) instead of O(n * k)."""
    diff = [0] * (n + 1)              # one spare slot so hi + 1 never overflows the array
    for lo, hi, delta in updates:
        diff[lo] += delta             # 1. the effect starts at lo...
        diff[hi + 1] -= delta         # 2. ...and is cancelled just after hi
    out = []
    running = 0
    for i in range(n):
        running += diff[i]            # 3. a prefix sum of the diffs rebuilds the values
        out.append(running)
    return out




if __name__ == "__main__":
    assert apply_range_adds(6, [(1, 3, 2), (2, 5, 3), (0, 0, -1)]) == [-1, 2, 5, 5, 3, 3]
    assert apply_range_adds(3, []) == [0, 0, 0]
    # Cross-check against the slow way.
    ups = [(0, 4, 1), (2, 2, 7), (3, 4, -2)]
    slow = [0] * 5
    for lo, hi, d in ups:
        for i in range(lo, hi + 1):
            slow[i] += d
    assert apply_range_adds(5, ups) == slow
    print("ok")

Try it. Each update touches exactly two cells of diff, whether the range is one cell or all of them:

Difference array: two writes per range update
sandbox
diff (length n + 1): what each update writes
0
0
2
0
0
0
0
-2
0
012345678
values = running sum of diff (rebuilt once, at the end)
0
0
2
2
2
2
2
0
01234567
updates1
diff writes2
brute-force writes5
rebuild adds8
Latest update: +2 on [2..6]. It wrote only diff[2] += 2 (the effect switches on) and diff[7] −= 2 (it switches off). Long ranges cost the same as short ones.
log: +2@[2..6]
diff[lo] += deltadiff[hi+1] −= deltacells the latest update changedrebuilding

Prefix sums plus a hash map (the idea, in words)

Section titled “Prefix sums plus a hash map (the idea, in words)”

A range sum is a difference of two prefixes: sum(i..j) = P[j+1] − P[i]. So “is there a range ending at j with sum k?” becomes “have I already seen a prefix equal to P[j+1] − k?”. That is a hash-map lookup, O(1). Scan left to right, keep a map from prefix value to whatever you need about it (how often it occurred, where it first occurred), and query before you insert.

This is the tool when values can be negative, which breaks the sliding window. Remember to seed the map with the empty prefix (0), which plays the same role as P[0].

What it costs

Section titled “What it costs”
Build Per query Per update Space
Re-sum the range each time none O(n) O(1) O(1)
Prefix array O(n) O(1) O(n) (rebuild) O(n)
2-D prefix array (R × C) O(R·C) O(1) O(R·C) O(R·C)
Difference array, k updates O(n) read at end O(1) O(n)
Fenwick / segment tree O(n) O(log n) O(log n) O(n)

The trade-off to say out loud: a prefix array is perfect for static data. Each point update shifts every later prefix, so it costs O(n). If updates and queries are interleaved, reach for a Fenwick tree or segment tree, which make both O(log n).

With q queries, brute force is O(n·q). For n = q = 10⁵ that’s 10¹⁰ operations, far too slow. Prefix sums make it O(n + q) = 2·10⁵.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Indicator prefix sums. Prefix-sum 1 if xs[i] is a vowel else 0 to answer “how many vowels in s[i..j]” in O(1). One array per category you count.
  • Prefix XOR / product / min? XOR works exactly like sum (it is its own inverse: X[j+1] ^ X[i]). Products work only without zeros (division is the inverse). Min and max do not: there is no way to “subtract” a minimum. Use a sparse table or segment tree for range min.
  • Prefix and suffix passes. Some problems need “everything to my left” and “everything to my right” for each index. Compute a left-to-right pass and a right-to-left pass, then combine.
  • 2-D difference arrays. Add v to a sub-rectangle with four writes (+v, −v, −v, +v at the corners), then a 2-D prefix sum rebuilds.
  • Sweep line counting. Sort (time, +1) and (time, −1) events and run a running total: the maximum is the peak overlap. This is a difference array over sparse coordinates. See sweep line.

Pitfalls

Section titled “Pitfalls”
  • Off-by-one. With the n + 1 layout, the range [i..j] is P[j+1] − P[i]. Write that formula down before coding and test it on a one-element range.
  • Overflow. n values of up to 10⁹ sum to 10¹⁴. Use long in C#. In TS, number is exact only up to 2⁵³ ≈ 9·10¹⁵; beyond that use bigint. Python ints don’t overflow. See math.
  • Mutating the input. Building the prefix array in place (xs[i] += xs[i-1]) saves memory but destroys the original. Say so if you do it.
  • Forgetting the empty prefix in the hash-map variant. Without {0: …} seeded, ranges that start at index 0 are missed.
  • Difference array bounds. diff[hi + 1] needs a spare slot, or a guard when hi is the last index.
  • Using it with updates. If the array changes between queries, a prefix array silently goes stale.

In the interview

Section titled “In the interview”
  • Ask: how many queries, and does the array change between them? That decides prefix array vs Fenwick tree vs brute force.
  • Ask about negative values before choosing between a sliding window and prefix sums.
  • State the definition out loud: “P[k] is the sum of the first k elements, so P[0] is 0 and the range i..j is P[j+1] minus P[i].” It shows you have the off-by-one under control.
  • Likely follow-ups: “What if the data is a grid?” (2-D), “What if updates are interleaved with queries?” (Fenwick or segment tree), “Can you do it in O(1) extra space?” (in place, if mutating is allowed).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
With P built as P[0] = 0 and P[k+1] = P[k] + xs[k], which expression gives xs[2] + xs[3] + xs[4]?
Check yourself
pick one
You get 10^5 range-add updates on an array of 10^5 zeros, and only then must print the final array. What is the best total cost?
Check yourself
pick one
Can you answer 'minimum of xs[i..j]' in O(1) with a prefix array of running minimums?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • Equilibrium index: the index where the sum on the left equals the sum on the right.
  • Count the vowels in many substring ranges of one fixed string.
  • Given bookings (first_row, last_row, seats), report seats booked per row.
  • Sum of a sub-matrix, for many queries on a fixed matrix.
  • Maximum number of overlapping intervals at any point (difference array over the timeline).

Go deeper

Section titled “Go deeper”
  • cp-algorithms: Fenwick tree, for when prefix sums need updates too, including range-update tricks built on difference arrays.
  • Competitive Programmer’s Handbook (Laaksonen), ch. 9 “Range queries”: prefix sums, 2-D prefix sums and sparse tables.
  • USACO Guide: Prefix Sums and More on Prefix Sums: 2-D sums and difference arrays with worked problems.
Section titled “Related”
Sliding windowRange sums when values are non-negative and you want O(1) space.
Hash mapsThe lookup that turns prefix sums into 'find a range with sum k'.
Segment and Fenwick treesRange queries when the array also changes.
Sweep lineDifference arrays over sorted events.