Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 63 ยท Data Structures in Contest Practice

Prefix Sums and Difference Arrays

Answer range queries in O(1) and apply range updates in O(1) with prefix sums and difference arrays, in 1D and 2D, plus offline counting by sweeping.

If a problem asks for the sum of a segment many times, adding the elements each time costs O(n) per query and O(n * q) in total, which is far too slow when both are 10^5. Prefix sums pay O(n) once and then answer every query in O(1). Their mirror image, the difference array, does the opposite job: it applies many "add v to every element of a segment" updates in O(1) each and rebuilds the final array in a single pass.

These two tools are so cheap and so common that they decide whether many "medium" problems are easy. This lesson covers both in one and two dimensions, shows how to use them for offline counting, and lists the indexing habits that prevent off-by-one errors. The basic idea is also in Prefix Sums; here we use it as a contest weapon.

Prefix sums and range queries

Define P[0] = 0 and P[i+1] = P[i] + a[i], so P has n + 1 entries and P[i] is the sum of the first i elements. Then the sum of a[l..r] (inclusive, 0-based) is

P[r + 1] - P[l]

Making the array one longer, with a zero in front, removes the special case for l = 0. Adopt this convention once and never mix it with a 1-based variant halfway through a solution.

Prefix sums work for anything with an inverse: sums, XOR (the inverse is XOR itself), counts of a given value, counts of a property such as "is a vowel" or "is greater than 5". They do not work directly for max or min, which have no inverse; those need a sparse table or segment tree (see Fenwick and Segment Trees for Contests).

Prefix sums also solve "count subarrays with sum k" in O(n): a subarray a[l..r] has sum k when P[r+1] - P[l] == k, so for each r you need the number of earlier prefixes equal to P[r+1] - k, which a dictionary keeps.

Python Range sums and subarrays with a given 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.

Difference arrays and range updates

Suppose you start with all zeros and receive updates "add v to every position in [l, r]". Doing them directly costs O(n) per update. Instead store the differences D[i] = a[i] - a[i-1]. A range add changes only two differences: add v at D[l] and subtract v at D[r + 1]. When all updates are done, a single prefix sum over D recovers the array.

The size trick: allocate n + 1 entries so that D[r + 1] is always legal, even for r = n - 1.

Two facts make the difference array a favorite:

  • It is the inverse of the prefix sum: prefix(difference(a)) == a.
  • Updates and queries can be separated into phases (all updates first, then all queries). If they are interleaved, you need a Fenwick tree, not a difference array.

The same idea counts overlap. Given a list of intervals, adding 1 at each start and subtracting 1 just past each end tells you, after one prefix pass, how many intervals cover each point. The maximum of that array is the deepest overlap, such as the maximum number of meetings in progress at once.

flowchart LR
    A["Updates: add v on l..r"] --> B["D[l] += v, D[r+1] -= v"]
    B --> C["Prefix sum of D"]
    C --> D["Final array"]

A difference array turns each range update into two point updates, then one sweep rebuilds the array.

Python Range updates and interval overlap

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

For a grid g with R rows and C columns, build P with R + 1 rows and C + 1 columns, where P[i][j] is the sum of the rectangle covering rows 0..i-1 and columns 0..j-1:

P[i+1][j+1] = g[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]

The subtraction removes the overlap that was counted twice. To get the sum of the rectangle with rows r1..r2 and columns c1..c2 (inclusive), use inclusion-exclusion:

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

The 2D difference array is the exact analog: to add v to a rectangle, change four corners: D[r1][c1] += v, D[r1][c2+1] -= v, D[r2+1][c1] -= v, D[r2+1][c2+1] += v. After all updates, take the 2D prefix sum of D. Allocate one extra row and one extra column.

Python 2D prefix sums and rectangle updates

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.

Offline counting

Many queries do not need an online data structure. If you may read all queries first (the usual situation in a contest), you can answer them in a smart order. Two patterns come up constantly:

  • Counting by value. To answer "how many elements are <= x" for many x, build a frequency array over the value range and take its prefix sums, or sort and use bisect. This is prefix sums over values instead of positions.
  • Events and sweeps. Turn each interval into a "+1 at start, -1 after end" pair, sort the events (or use a difference array when coordinates are small), and sweep. A query that asks "how many intervals contain the point x" is a prefix sum of the events.

If the coordinates are huge, compress them first, which is covered in Sorting, Events and Sweeps.

Habits that prevent bugs

  • Make P one element longer than a and always write ranges as inclusive l..r with P[r+1] - P[l].
  • Use n + 1 (or n + 2 in 1-based code) slots in difference arrays.
  • Prefix sums in Python can grow large; there is no overflow, but if the answer must be printed modulo something, reduce as you go.
  • If the array changes between queries, prefix sums are stale. Rebuild them, or switch to a Fenwick tree.
  • Test the technique against the naive loop on tiny random inputs; the examples above show how in five lines.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. With P[0] = 0 and P[i + 1] = P[i] + a[i], what is the sum of a[l..r] inclusive?

    P[r + 1] covers a[0..r], P[l] covers a[0..l-1]. Their difference is exactly a[l..r], and the leading zero in P makes l = 0 work without a special case.
  2. 2. You receive 10^5 updates of the form 'add v to a[l..r]' and then 10^5 point queries. What is the best approach?

    Each update costs O(1) in a difference array, and a single O(n) prefix sum afterwards gives all final values. This works because updates all come before the queries.
  3. 3. In the 2D prefix formula P[i+1][j+1] = g[i][j] + P[i][j+1] + P[i+1][j] - P[i][j], why is P[i][j] subtracted?

    The rectangle above and the rectangle to the left both contain the rectangle ending at (i-1, j-1). Inclusion-exclusion removes the double count.
  4. 4. Which operation can NOT be answered directly with a prefix array?

    Prefix arrays rely on an inverse operation (subtraction for sums, XOR for XOR). Maximum has no inverse, so you need a sparse table or segment tree.
  5. 5. Why allocate n + 1 entries in a difference array?

    A range ending at the last element subtracts v at index r + 1 = n. Without the extra slot that write would fail.

Summary

  • Prefix sums with a leading zero give O(1) range sums: P[r+1] - P[l].
  • A dictionary of earlier prefixes counts subarrays with a given sum in O(n).
  • Difference arrays make range updates O(1): D[l] += v, D[r+1] -= v, then one prefix pass.
  • In 2D, use inclusion-exclusion for queries and four corner updates for rectangles; allocate one extra row and column.
  • Offline counting uses prefix sums over values or over sorted events.
  • Updates and queries must be separated into phases; otherwise use a Fenwick tree.

Next: Monotonic Stacks, Heaps and Deques in Contests