PrefixAlgorithmaka cumulative sum, running total, partial sums, scan

Prefix Sum

Precompute P[i] = a[0] + … + a[i-1] once so that any subarray sum a[l..r] is P[r+1] − P[l] in O(1).

▶ VisualizePattern: HashingPractice (3)
Progress

Overview

A prefix sum array P of length n + 1 stores the running total of the input: P[0] = 0 and P[i] = P[i-1] + a[i-1]. After this O(n) pass, the sum of any contiguous range a[l..r] is P[r+1] − P[l], computed in O(1). It converts "many range-sum queries on a static array" from O(n) each to O(1) each, and it converts "find a subarray with sum k" into "find two prefix values that differ by k", which a Hash Map answers in one pass.

The same trick works for any invertible associative operation: sums, XOR (Prefix XOR), products modulo a prime (with modular inverses), counts of a property ("number of vowels up to i"). It does not work for max/min because there is no way to "subtract" the contribution of a prefix — that needs a Sparse Table or Segment Tree.

contiguoussubarrayrange queryO(1) queryimmutablecumulative

Intuition

A mental model before the formal terms.

Think of a car odometer. To know how far you drove between mile markers l and r, you do not re-measure the road — you read the odometer at both points and subtract. The odometer is the prefix sum: a single number at each position that already encodes everything before it.

For "subarray with sum k", the picture is the same odometer with a question: "was there an earlier reading exactly k less than the current one?" Keep the earlier readings in a hash map and the answer is one lookup per step.

How it works

  1. Allocate P of length n + 1 with P[0] = 0.
  2. For i from 1 to n: P[i] = P[i-1] + a[i-1]. P[i] is the sum of the first i elements.
  3. Range query sum(l, r) (inclusive, 0-based): return P[r+1] − P[l].
  4. Subarray-sum-equals-k counting: scan left to right with a running P; maintain a map count[value] of how many earlier prefixes equal value, seeded with count[0] = 1. At each step add count[P − k] to the answer, then increment count[P].
  5. Balance / pivot problems: "left sum equals right sum" at index i is P[i] == total − P[i+1].

Why it works

Telescoping: P[r+1] − P[l] = (a[0] + … + a[r]) − (a[0] + … + a[l-1]) = a[l] + … + a[r]. Every element outside [l, r] appears in both terms and cancels. The P[0] = 0 sentinel makes l = 0 a special case of the same formula rather than an exception.

Hash-map counting: a subarray a[l..r] has sum k exactly when P[r+1] − P[l] = k, i.e. P[l] = P[r+1] − k. When the scan is at r, every l ≤ r has already been recorded in the map, so count[P[r+1] − k] is precisely the number of valid left endpoints for this right endpoint. Summing over all r counts every subarray exactly once. Seeding count[0] = 1 accounts for l = 0.

This works with negative numbers — unlike Sliding Window (Variable Size) — because it never relies on monotonicity; it only relies on subtraction being the inverse of addition.

Recognition

How to tell a problem wants this.

  • "Sum of elements between indices `i` and `j`", "range sum query", "immutable" array, "many queries" — q queries with n, q ≤ 10^5 make O(n·q) impossible and O(n + q) the target.
  • "Subarray sum equals k", "number of contiguous subarrays whose sum is divisible by k", "longest subarray with sum k" — especially when values can be negative (which rules out a sliding window).
  • "Pivot index", "equilibrium index", "split array into two parts with equal sum", "left sum equals right sum".
  • "Count of x in the range [l, r]", "number of 1s up to index i" — prefix counts.
  • Any O(n²) double loop over (l, r) whose inner work is summing a[l..r] — the prefix array collapses the inner sum.
“have you seen this before” → Hashing“sum of subarray” → Prefix Sum

Interactive visualization

Play, step, change the input. ← → and space work too.

a
3
0
1
1
4
2
1
3
5
4
9
5
2
6
6
7
P (prefix sums)
0
0
1/13Build P where P[i] is the sum of the first i elements. P[0] = 0 (empty prefix) so every query has a clean left endpoint.
Being addedQueried rangePrefix entries usedAnswer
PseudocodeLearn Prefix Sum →
1P[0] = 0
2for i in 0 .. n-1: P[i+1] = P[i] + a[i]
3query(l, r) = P[r+1] - P[l]
Variables
n8
Complexity
best O(n)
avg O(n)
worst O(n)
space O(n)
Speed

Pseudocode

1P = array of n + 1 zeros
2for i in 1..n: P[i] = P[i-1] + a[i-1]
3range_sum(l, r) = P[r+1] - P[l]
4# count subarrays with sum k
5seen = {0: 1}, run = 0, count = 0
6for x in a:
7  run += x
8  count += seen[run - k]
9  seen[run] += 1
10return count

Implementations

1# Subarray Sum Equals K: count contiguous subarrays summing to k (values may be negative)
2from collections import defaultdict
3 
4 
5def subarray_sum(a: list[int], k: int) -> int:
61 · Map from prefix value to how many times it has occurred; seed the empty prefix
7    seen: defaultdict[int, int] = defaultdict(int)
8    seen[0] = 1
92 · Running prefix sum and answer
10    run = 0
11    count = 0
12    for x in a:
133 · Extend the prefix by the current element
14        run += x
154 · Every earlier prefix equal to run - k closes a subarray with sum k
16        count += seen[run - k]
175 · Record this prefix for later right endpoints
18        seen[run] += 1
19    return count
Walkthrough
  1. defaultdict(int) returns 0 for missing keys, so seen[run - k] is a safe read-only lookup (it does insert a 0 entry, which is harmless but grows the dict).
  2. seen[0] = 1 seeds the empty prefix.
  3. Python ints are unbounded, so the prefix sum never overflows.
  4. Lookup before record — swapping the two lines breaks the k == 0 case.
  5. Iterating for x in a reads each element once.
Complexity (this implementation)
time O(n) · space O(n)

Every seen[run - k] read on a defaultdict inserts a 0 entry; use seen.get(run - k, 0) on a plain dict to avoid the extra entries.

Language notes
  • itertools.accumulate(a) produces the prefix sums lazily; list(accumulate(a, initial=0)) (3.8+) gives the sentinel-prefixed array for the range-query variant.
  • Counter works identically to defaultdict(int) here.
  • Big-int arithmetic is slower than fixed-width, but for prefix sums within 64 bits CPython uses a fast path.
Common mistakes in this language
  • Using a plain dict with seen[run - k] and getting a KeyError.
  • Building the prefix list with sum(a[:i]) in a loop — O(n^2).
  • Forgetting seen[0] = 1.
Language differences that matter here
  • Prefix-sum width: C++ must key the map by long long (an int prefix overflows silently into UB); JS/TS doubles are exact to 2^53 (about 9e15) — enough for n·max|a| up to ~1e15, beyond that use BigInt; Python ints never overflow.
  • Lookup semantics: C++ unordered_map::operator[] and Python defaultdict both insert on read; C++ find and Python dict.get(k, 0) do not. JS/TS Map.get never inserts.
  • Map keys: JS objects stringify numeric keys, so Map is required for correctness and speed; Python dicts and C++ unordered_map key on the number directly.
  • Building the prefix array: Python has itertools.accumulate(a, initial=0); C++ has std::partial_sum / std::inclusive_scan; JS/TS need a manual loop (reduce with an accumulator array also works).

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

O(n) build, O(1) per range query. The hash-map counting variant is O(n) time and O(n) space in a single pass.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Static array with many range-sum (or range-count, range-XOR) queries.
  • Subarray problems with a sum/divisibility target where values may be negative.
  • Balance/pivot problems comparing left-of-i and right-of-i totals.
  • As a building block: 2D Prefix Sum, Difference Array, Kadane's Algorithm reformulated as P[r] − min(P[l]).
Avoid it when
  • The array is updated between queries — each point update invalidates O(n) prefix entries; use a Fenwick Tree or Segment Tree for O(log n) updates.
  • The query is max/min over a range — subtraction does not undo max; use Sparse Table (static) or Segment Tree.
  • A single query on an array — a direct O(n) scan is simpler and uses no extra memory.
  • Longest/shortest subarray under a monotone constraint with non-negative values — Sliding Window (Variable Size) does it in O(1) space.

Alternatives

Sliding Window (Variable Size)Fenwick TreeSegment TreeSparse TableDifference Array
Compare: Prefix Sum vs Segment Tree

Common mistakes

  • Using a length-n prefix array with P[0] = a[0] and then special-casing l = 0 everywhere; the n + 1 array with P[0] = 0 removes the special case.
  • Computing P[r] − P[l] instead of P[r+1] − P[l] (excludes a[r]).
  • Forgetting seen[0] = 1 in the counting variant — subarrays starting at index 0 are missed.
  • Incrementing seen[run] before looking up seen[run − k] when k = 0, which counts the empty subarray.
  • Overflow: prefix values grow to n · max|a|; use 64-bit integers in Java/C++/Go.
  • For "divisible by k" variants, forgetting to normalize negative remainders (((run % k) + k) % k).

Interview patterns

  • Range Sum Query - Immutable (the NumArray class).
  • Subarray Sum Equals K and Continuous Subarray Sum (prefix mod k in a hash map).
  • Find Pivot Index / Product of Array Except Self (prefix and suffix products).
  • Contiguous Array: map 0→−1, find the longest subarray with prefix sum 0 via first-occurrence map.
  • Maximum Subarray as max(P[r] − min_{l ≤ r} P[l]) — an alternative derivation of Kadane's Algorithm.
  • Count of vowels / 1s in a range via a prefix count array.
Interview questions on this
Mock interviews

Example problems

Subarray Sum Equals KmediumProduct of Array Except SelfmediumMaximum Subarraymedium