Prefix Sum

01 / The shared mechanism

Pay O(N) once to build a cumulative table — every range query that follows reduces to a constant-time subtraction. Flip the trick inside-out and you get cheap range updates instead.

01 / The one-sentence essence
Pay O(N) once to build a running-total table — every range query that follows is a single subtraction of two prefixes.
Problemsum of arr[l..r] in O(1)Input[3, 1, 2, 5, 4, 2, 1, 3]Queryarr[2..5]
prefix
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
arr
3
0
1
1
2
2
5
3
4
4
2
5
1
6
3
7
Two arrays: input arr below, prefix table prefix above. The prefix is one cell longer.
step
0 / 14
phase
build
result
·
0 / 14

02 / The pattern signature

# build the prefix table onceprefix[0] ← 0for i in 0..n−1:prefix[i+1] ← prefix[i] + arr[i]# query: sum of arr[l..r] in O(1)rangeSum(l, r) ← prefix[r+1] − prefix[l]# prefix[i] = sum of arr[0..i−1] — the "+1 offset" lets l = 0 work uniformly

03 / When to recognize this pattern

"sum of arr[l..r]"
The literal canonical signal. The array is fixed; queries can be in any order, any count. Build once, query forever.
"running total"
Any quantity that's additive over the array — sum, count, XOR — admits the same trick.
"many queries"
The pattern only pays off when query count ≥ 2. A single query is no faster than scanning the slice directly. The amortization is over the queries.
"average / mean over a window"
Average is just sum / length — same machinery.

04 / Common pitfalls

i.
Off-by-one on the +1 offset.
Prefix is one cell longer than the input: prefix[0] = 0, and prefix[i+1] is the sum of arr[0..i]. The query then is prefix[r+1] − prefix[l] with inclusive bounds. Skip the offset and you'll either miss the first element or undercount on every query.
ii.
Mutating the array after building the prefix.
The prefix is a snapshot. If arr changes, every cell of prefix downstream of the change is now stale. For mutable arrays reach for a segment tree or Fenwick instead.
iii.
Integer overflow on long arrays.
The prefix grows monotonically; in languages with fixed-width ints (Java, C++), use long for the table even if input values fit in int.

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Range Sum Query — Immutable— LC 303easy→02Find Pivot Index— LC 724easy→03Product of Array Except Self— LC 238medium→04Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold— LC 1343medium→

— / When to use which

1-D linear
Use when you have many range-sum queries on a fixed array.
range-sum · running-total · LC 303
2-D grid
Use for rectangle queries on a matrix — inclusion-exclusion on the corners.
matrix-region · block-sum · LC 304
difference
Flip the direction: many range updates, then a single read of every cell.
range-add · car-pooling · flight-bookings
hash map
Count subarrays whose sum hits a target — prefix + map of seen prefixes.
subarray-sum-k · divisible-by-k · LC 560