Vibe Engines Learn
Algorithm · Arrays & Windows

The Running Total.

Don't memorize prefix sums — watch the running total build. Add up the array once into a cumulative list where P[i] is the total of everything up to i. After that one O(n) pass, the sum of any range is a single subtraction — P[j] − P[i−1] — answered in O(1), no matter how many times you ask.

cumulative sum · range query · O(1) · preprocessing
PREFIX P[i]

The total of A[0..i] — everything up to and including index i.

BUILD

P[i] = P[i−1] + A[i], one pass, O(n).

RANGE SUM

sum(i..j) = P[j] − P[i−1]. One subtraction.

PAYOFF

m queries cost O(n + m), not O(n·m).

prefix-sums.sim — build, then range queries
Ready

Top row is the array A; bottom row is the prefix sums P. Press Step to build P cell by cell — each is the one before it plus the value above — then answer range-sum queries with a single subtraction.

P[i] = P[i−1] + A[i]
Build
Phase
O(n)
Cost

Precompute once, subtract forever

Summing a range the naive way re-adds every element each time you ask — fine for one query, terrible for thousands. Prefix sums pay the cost once: a single sweep builds a running total, and from then on the sum of any contiguous slice is the total up to the end of the slice minus the total just before it starts. Everything before the range cancels, leaving exactly the range.

01

Build the prefix array

P[0] = A[0], then P[i] = P[i−1] + A[i]. One O(n) pass, O(n) space.

02

Answer a range query

sum(i..j) = P[j] − P[i−1] (treat P[−1] as 0). One subtraction — O(1).

03

Why it works

P[j] counts everything through j; P[i−1] counts everything before i. Subtract and only the range i..j survives.

04

Extend it

2-D prefix sums (integral images) answer sub-rectangle sums with four lookups; a Fenwick tree adds O(log n) updates.

Build
O(n)
Range query
O(1)
m queries total
O(n + m)
Space
O(n)

The catch: prefix sums assume the array does not change. Update one value and every prefix after it is stale, costing O(n) to fix — which is exactly the gap a Fenwick (binary indexed) tree or a segment tree fills, trading O(1) queries for O(log n) queries and O(log n) updates.

SOLVE IT YOURSELF

Solve it: range sums in O(1)

This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement range_sum(nums, queries): precompute a prefix-sum array once, then answer each query [l, r] with the inclusive sum of nums[l..r] in O(1). Return the list of answers. Building the prefix array is O(n); each query is then a single subtraction.

HINTS — 4 IDEAS
  1. Build pre where pre[i] = sum of the first i elements, with pre[0] = 0.
  2. Then pre[i+1] = pre[i] + nums[i] — one pass, O(n).
  3. The inclusive sum of nums[l..r] is pre[r+1] − pre[l].
  4. Map every query through that formula — each is O(1), no re-scanning.
CPython · WebAssembly

Check yourself

1 · How is the prefix array built?

Each prefix is the previous running total plus the current value — a single cumulative pass.

2 · What is the sum of the range i..j using prefix sums?

Total up to j minus total before i leaves exactly the range i..j — one subtraction, O(1).

3 · When do prefix sums stop being ideal?

An update invalidates every later prefix (O(n) to rebuild); a Fenwick or segment tree handles updates in O(log n).

Questions

Why keep P[i−1] instead of just P[i]?

Because a range starting at i needs everything before i removed. P[i−1] is precisely that total, so subtracting it strips off the prefix and leaves the range. Using an extra leading zero (P of length n+1) is a common trick to avoid the i=0 special case.

What problems use prefix sums?

Range-sum queries, subarray-sum-equals-k (with a hash map of prefix counts), equilibrium and pivot indices, running averages, and — in 2-D — image box filters and sub-rectangle sums.

How does subarray-sum-equals-k use them?

As you scan, keep a hash map of how many times each prefix sum has occurred. At index j, the number of subarrays ending at j with sum k is the count of prefix sum P[j] − k seen so far — turning an O(n²) search into O(n).

One pass up front, O(1) forever after.

Build the running total once, then every range is a subtraction. Preprocessing that pays for itself.

← All algorithms Sliding Window → Two Pointers → Big-O Cheatsheet →
Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →