02 Prefix sums and difference arrays / Lesson 1 of 1

Prefix sums and difference arrays

15 min · +10 XP · 2 exercises · 4 questions

Read the text15 min

Exercises0/2

Quiz4 q

Quick answer

What is a prefix sum array used for?

A prefix sum array stores p[i] = a[1] + … + a[i], with p[0] = 0. Built once in O(n), it answers any range sum a[l..r] as p[r] − p[l − 1] in O(1), so q queries cost O(n + q) instead of O(n · q). Its inverse, the difference array, applies range updates in O(1) each.

Two problems, one idea. Many range-sum queries on a fixed array, and many range updates followed by one read. Done element by element both are O(n · q) — 10¹⁰ at the limits.

Prefix sums: precompute, then subtract

vector<ll> p(n + 1, 0);              // p[0] = 0
for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + a[i];
// sum of a[l..r]
ll s = p[r] - p[l - 1];

p[i] is the sum of the first i elements. Building it is one pass, O(n).
A range is "everything up to r" minus "everything before l".
p[0] = 0 means l = 1 needs no special case.
long long: a prefix of 2·10⁵ values of 10⁹ is 2·10¹⁴.

Build the prefix array once, answer every range in O(1)

a = [3, 1, 4, 1, 5, 9, 2], query a[3..6]

p[i] will hold a[1] + … + a[i]. Start with p[0] = 0, the sum of nothing — it is what lets a range starting at 1 need no special case.

0:01 / 0:17Step 1 of 6

Transcript · 6 steps

Difference arrays: update now, sum later

Run the idea backwards. To add v to a[l..r], mark only where the change starts and where it stops:

vector<ll> d(n + 2, 0);
d[l] += v;                           // the change starts at l
d[r + 1] -= v;                       // and stops after r
// after every update:
ll run = 0;
for (int i = 1; i <= n; ++i) { run += d[i]; a[i] = run; }

Two writes per update, however long the range.
One running sum rebuilds the whole array: O(n + m) in total.
d has n + 2 slots so an update ending at n still has somewhere to stop.

Many range updates, then one prefix sum: the difference array

n = 6; +3 on 1..3, +2 on 2..5, +1 on 4..6

Add v to every element of [l, r] by writing d[l] += v and d[r + 1] −= v. d has a slot n + 1 = 7, so an update that ends at n still has somewhere to stop.

0:01 / 0:26Step 1 of 9

Transcript · 9 steps

Which one, when?

Many queries, no updates → prefix sums.
Many updates, then one read → difference array.
Updates and queries mixed → neither; a Fenwick or segment tree (later in this track).
Rectangles of a grid → 2D prefix sums: big block − top strip − left strip + corner.

Prefix array, difference array, or neither? — Pick the tool that makes the problem fit the time limit.

2·10^5 queries "sum of a[l..r]" on an array that never changes. Prefix sums. Build once in O(n), answer each query with one subtraction: O(n + q).
2·10^5 updates "add v to a[l..r]", then print the array once. Difference array. Two writes per update and one running sum at the end: O(n + m).
Updates and sum queries interleave, each update visible to the next query. Neither — a Fenwick or segment tree. A changed element shifts O(n) prefixes. A tree handles both operations in O(log n).
Many queries for the sum of a rectangle in a fixed grid. 2D prefix sums. Four lookups per rectangle: big block, minus two strips, plus the corner.
Count subarrays whose sum is exactly k; values may be negative. Prefix sums with a hash map of earlier prefixes. p[r] − p[l − 1] = k means looking up p[r] − k among the earlier prefixes. A window needs non-negative values.

More practice

Range Sum Query - Immutable — the prefix array itself.
Find Pivot Index — left sum against right sum.
Subarray Sum Equals K — prefixes in a hash map.
Corporate Flight Bookings — a difference array.
Car Pooling — range updates, then a scan.

Common questions

What is a difference array?

The inverse of a prefix array. To add v to every element of [l, r], write d[l] += v and d[r + 1] −= v; after all updates, one running sum over d gives the final array. m updates cost O(n + m) instead of O(n · m).

Why does the prefix array start with p[0] = 0?

It is the sum of no elements, and it makes a range starting at index 1 the same formula as every other range: a[1..r] = p[r] − p[0]. Without it, every query with l = 1 needs a special case.

When can't I use prefix sums?

When updates and queries are interleaved. One changed element shifts every later prefix, so each update costs O(n). A Fenwick tree or a segment tree supports both operations in O(log n).

How do 2D prefix sums work?

P[i][j] holds the sum of the block above and left of (i, j). A rectangle is the big block minus the strip above, minus the strip to the left, plus the corner both strips removed: four lookups, O(1).

Mark as readSign in to keep your place.

Prefix Sums and Difference Arrays for Competitive Programming

Build a prefix array in O(n) to answer range-sum queries in O(1), and use a difference array to apply many range updates with two writes each, in C++.

Course: Competitive Programming study plan
Module: Prefix sums and difference arrays
Kind: Lesson
Reading time: 15 min
Runtime: Clang 18 · C++20

What is a prefix sum array used for?

Lesson

Two problems, one idea. Many range-sum queries on a fixed array, and many range updates followed by one read. Done element by element both are O(n · q) — 10¹⁰ at the limits.

Prefix sums: precompute, then subtract

vector<ll> p(n + 1, 0);              // p[0] = 0
for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + a[i];
// sum of a[l..r]
ll s = p[r] - p[l - 1];

p[i] is the sum of the first i elements. Building it is one pass, O(n).
A range is "everything up to r" minus "everything before l".
p[0] = 0 means l = 1 needs no special case.
long long: a prefix of 2·10⁵ values of 10⁹ is 2·10¹⁴.

Build the prefix array once, answer every range in O(1). Example: a = [3, 1, 4, 1, 5, 9, 2], query a[3..6]

p[i] will hold a[1] + … + a[i]. Start with p[0] = 0, the sum of nothing — it is what lets a range starting at 1 need no special case.
p[1] = p[0] + a[1] = 0 + 3 = 3. One addition per slot: the previous total plus the new element.
p[2] = p[1] + a[2] = 3 + 1 = 4. One addition per slot: the previous total plus the new element.
p[3] = p[2] + a[3] = 4 + 4 = 8. One addition per slot: the previous total plus the new element.
The loop runs to the end the same way, so the whole prefix array costs O(n): p = [0, 3, 4, 8, 9, 14, 23, 25].
Now any range is two lookups. a[3..6] is everything up to 6 minus everything up to 2: p[6] − p[2] = 23 − 4 = 19, which is 4 + 1 + 5 + 9. O(1) per query.

Difference arrays: update now, sum later

Run the idea backwards. To add v to a[l..r], mark only where the change starts and where it stops:

vector<ll> d(n + 2, 0);
d[l] += v;                           // the change starts at l
d[r + 1] -= v;                       // and stops after r
// after every update:
ll run = 0;
for (int i = 1; i <= n; ++i) { run += d[i]; a[i] = run; }

Two writes per update, however long the range.
One running sum rebuilds the whole array: O(n + m) in total.
d has n + 2 slots so an update ending at n still has somewhere to stop.

Many range updates, then one prefix sum: the difference array. Example: n = 6; +3 on 1..3, +2 on 2..5, +1 on 4..6

Add v to every element of [l, r] by writing d[l] += v and d[r + 1] −= v. d has a slot n + 1 = 7, so an update that ends at n still has somewhere to stop.
Update +3 on 1..3: d[1] += 3 and d[4] −= 3. Two writes whatever the length of the range — d is now [3, 0, 0, −3, 0, 0, 0].
Update +2 on 2..5: d[2] += 2 and d[6] −= 2. Two writes whatever the length of the range — d is now [3, 2, 0, −3, 0, −2, 0].
Update +1 on 4..6: d[4] += 1 and d[7] −= 1. Two writes whatever the length of the range — d is now [3, 2, 0, −2, 0, −2, −1].
Then one prefix sum over d gives the array: a[1] = d[1] = 3. The +3 that starts at 1 is carried along by the running sum.
a[2] = a[1] + 2 = 5. d[2] nets every change here: +2 starts.
a[4] = a[3] − 2 = 3. d[4] nets every change here: +3 stops, +1 starts.
a[6] = 1. Each element is the sum of every change that started at or before it, minus every one that already stopped.
a = [3, 5, 5, 3, 3, 1], the same as applying each update element by element. 3 updates cost 6 writes plus one O(n) pass: O(n + q) instead of O(n · q).

Which one, when?

Many queries, no updates → prefix sums.
Many updates, then one read → difference array.
Updates and queries mixed → neither; a Fenwick or segment tree (later in this track).
Rectangles of a grid → 2D prefix sums: big block − top strip − left strip + corner.

Prefix array, difference array, or neither? — Pick the tool that makes the problem fit the time limit.

2·10^5 queries "sum of a[l..r]" on an array that never changes. Prefix sums. Build once in O(n), answer each query with one subtraction: O(n + q).
2·10^5 updates "add v to a[l..r]", then print the array once. Difference array. Two writes per update and one running sum at the end: O(n + m).
Updates and sum queries interleave, each update visible to the next query. Neither — a Fenwick or segment tree. A changed element shifts O(n) prefixes. A tree handles both operations in O(log n).
Many queries for the sum of a rectangle in a fixed grid. 2D prefix sums. Four lookups per rectangle: big block, minus two strips, plus the corner.
Count subarrays whose sum is exactly k; values may be negative. Prefix sums with a hash map of earlier prefixes. p[r] − p[l − 1] = k means looking up p[r] − k among the earlier prefixes. A window needs non-negative values.

More practice

Range Sum Query - Immutable — the prefix array itself.
Find Pivot Index — left sum against right sum.
Subarray Sum Equals K — prefixes in a hash map.
Corporate Flight Bookings — a difference array.
Car Pooling — range updates, then a scan.

Common questions

What is a difference array?

Why does the prefix array start with p[0] = 0?

It is the sum of no elements, and it makes a range starting at index 1 the same formula as every other range: a[1..r] = p[r] − p[0]. Without it, every query with l = 1 needs a special case.

When can't I use prefix sums?

When updates and queries are interleaved. One changed element shifts every later prefix, so each update costs O(n). A Fenwick tree or a segment tree supports both operations in O(log n).

How do 2D prefix sums work?

P[i][j] holds the sum of the block above and left of (i, j). A rectangle is the big block minus the strip above, minus the strip to the left, plus the corner both strips removed: four lookups, O(1).

Exercises

Range sum queries

Read an array of n integers and answer q queries: each gives l r (1-indexed) — print a[l] + … + a[r].

Constraints: 1 ≤ n, q ≤ 2·10⁵, -10⁹ ≤ aᵢ ≤ 10⁹, 1 ≤ l ≤ r ≤ n.

Input: n q, the array, then q lines l r. Output: one sum per line.

prints

15
5
4

Many range additions

An array of n zeros receives m updates. Update l r v adds v to every element from l to r (1-indexed). Print the array after all of them.

Constraints: 1 ≤ n, m ≤ 2·10⁵, 1 ≤ l ≤ r ≤ n, -10⁹ ≤ v ≤ 10⁹.

Input: n m, then m lines l r v. Output: the n final values on one line, separated by spaces.

prints

2 5 5 3 2

In this module: Prefix sums and difference arrays

← Checkpoint — Fast I/O and complexity budgets · Checkpoint — Prefix sums and difference arrays →