How does a range sum become O(1)?

Precompute P, where P[i] holds the sum of the first i + 1 elements. The sum of A[L..R] is then P[R] - P[L-1], because the shared prefix cancels. Building P costs O(N) once and every query afterwards is two lookups and a subtraction.

How do I avoid the L = 0 edge case?

Store P with a leading zero, so P[0] = 0 and P[i] is the sum of the first i elements. The query becomes P[R+1] - P[L] with no special case.

What happens if the array changes?

A single update invalidates every later prefix and costs O(N) to repair. With updates interleaved among queries, use a Fenwick tree or a segment tree, which do both in O(log N).

Prefix Sum

A prefix sum array answers range sum queries efficiently by storing the running total up to each index.

7 VALUES

BUILD

Prefix array P

Source array A

-1

P[0] = A[0] = 3. The first prefix is just the first element.

P[1] = P[0] + A[1] = 3 + 1 = 4.

Array

From

Intuition

Calculating the sum of a range [L, R] normally takes O(N) time. If we have many queries, this is slow. By pre-calculating cumulative sums, we can answer any range sum query in O(1) time.

Concept

Prefix Sum Array (P): P[i] stores the sum of A[0]...A[i].
Construction: P[i] = P[i-1] + A[i]. (O(N) time)
Range Query (L, R): Sum(L, R) = P[R] - P[L-1]. (O(1) time)

How it Works

Formula:

Sum(L, R) = Sum(0, R) - Sum(0, L-1)
Sum(L, R) = P[R] - P[L-1]

Note: If L=0, Sum(0, R) = P[R].

Step-by-Step Breakdown

Watch the visualization:

See how P[i] accumulates the sum.
Observe how the query uses subtraction to isolate the range sum.

Trace: A = [3, 1, 4, 1, 5, 9, 2, 6]

build P

One pass, P[i + 1] = P[i] + A[i], starting from P[0] = 0. The table is one slot longer than the array.

[0, 3, 4, 8, 9, 14, 23, 25, 31]

sum(2, 5)

P[6] - P[2] = 23 - 4. The first two elements are counted in both prefixes, so they cancel and only A[2..5] survives.

check

By hand, A[2..5] is 4 + 1 + 5 + 9. The subtraction did not approximate anything.

sum(0, 3)

P[4] - P[0] = 9 - 0. The leading zero is what makes a query starting at index 0 need no special case.

set A[3] = 7

Every entry from P[4] onward is now wrong by 6. Repairing the table means walking the rest of it, so an array that changes wants a Fenwick or segment tree instead.

O(N) per update

When to Use

Multiple range sum queries on a static array.
Finding subarrays with sum K.
2D Prefix Sums for submatrix queries.

When NOT to Use

If the array updates frequently (updating P takes O(N)). Use Fenwick Tree or Segment Tree instead.

How to Identify

"Range Sum", "Cumulative Sum", "Subarray Sum equals K".

Sample Problems

Range Sum Query - Immutable

Calculate the sum of elements of nums between indices i and j inclusive.

Subarray Sum Equals K

Find total number of continuous subarrays whose sum equals to k.

Preparing for interviews? This topic is also taught as a pattern:

Introduction to Prefix Sums

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Sliding Window

Kadane's Algorithm