THE PREFIX SUM one pass to precompute, then every range-sum in a single subtraction
Sum the values between any two positions, over and over, without re-adding them each time. The prefix sum makes one pass to build a running total P[k] = x₀+…+xk−1; thereafter any range sum is one subtraction: sum(i..j) = P[j+1] − P[i]. A structure computed once answers unboundedly many queries in O(1) each. It is the discrete integral — and its inverse, the difference (dart 323), is the discrete derivative. In two dimensions it becomes the summed-area table behind box blurs and Haar features. The one pass amortizes away all the re-summing a naive query would repeat.
THE TECHNIQUE build P once; sum(i..j) = P[j+1] − P[i], O(1) per query
An array and a range. The demo builds the prefix sums once and answers a range-sum query by one subtraction: live demo
HISTORY & CREDIT prefix sum / scan · a fundamental primitive
“Every range sum costs a fresh scan.” — one prefix pass turns all future range sums into a single subtraction each. Compute once, answer forever. cited
fundamental · the prefix sum (inclusive/exclusive scan), a primitive as old as computing with arrays. parallel · Blelloch (1990) formalized scan as a parallel primitive with an O(n)-work, O(log n)-depth algorithm. 2D · the summed-area table (Crow, 1984) — box filters and Viola–Jones features in O(1) per region. now · range queries, histogram equalization, GPU scans, competitive-programming bedrock.
A single accumulating pass, then subtraction answers every range. The discrete integral, banked. scan / summed-area
RECOMMEND FOR I-13 the O(1) range-sum, on the compiler
On the canonical compiler, over [3,1,4,1,5] the range sum of positions 1..3 is P[4]−P[1] = 9−3 = 6 — one subtraction:
$ i13 run op_prefixsum.i13 # sum(1..3) = P[4] - P[1]
RUN OK · 120 step(s) · peak stack 7 · call depth 5
range_sum = 6 -- one pass to build, one subtraction to query
Recommend: the prefix sum is the compute-once, answer-forever pattern — one streaming pass that amortizes away every future range scan. i13 answers sum(1..3)=6 by a single subtraction. The supplement to correctness: a correct naive query re-adds the range each time (O(n)/query); the prefix structure makes it O(1). It shares the “computed structure serves many queries” flavour with Stern-Brocot (a keeper) but here the structure is stored, not computed-on-demand — so it is a witness of the range-sum identity, not a keeper. The discrete integral, paired with its derivative next door (dart 323).