Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Prefix sums: trade one scan for constant-time ranges

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A prefix-sum array stores the sum of all values before each boundary. With an initial zero, the sum over half-open interval [left, right) is prefix[right] minus prefix[left]. Construction costs O(n) time and O(n) extra space; each valid range query costs O(1). The contract assumes the underlying values do not change after building the prefix table. If values update, the table becomes stale and rebuilding costs O(n); a Fenwick tree or segment tree serves frequent mixed updates and queries more efficiently. Half-open bounds make adjacent ranges compose without counting a boundary twice.

Operational case

A warehouse dashboard stores daily scanned parcel counts of 47, 31, 26, and 58. It needs the sum for days one through three, represented as [1, 4), which is 31 + 26 + 58 = 115. The first day remains outside the range. A table built from these four daily values answers many reporting windows cheaply. When a late scan changes day two from 26 to 29, the old prefix table cannot be used until rebuilt; returning its previous 115 would hide the correction.

Working Python program

python
daily_scans = [47, 31, 26, 58]
prefix = [0]
for scan_count in daily_scans:
    prefix.append(prefix[-1] + scan_count)
left_day, right_day = 1, 4
print(prefix[right_day] - prefix[left_day])
print(prefix)

Output

Output
115
[0, 47, 78, 104, 162]

Time, space, and tradeoff

The loop visits n values once and stores n + 1 totals. Query bounds must satisfy 0 <= left <= right <= n; an empty interval then returns zero. Negative counts may be valid adjustments, but they change whether a cumulative total is monotone. In fixed-width integer languages, check overflow before adding large measurements. A prefix array saves work when queries substantially outnumber updates and the input snapshot has an explicit revision.

Common Mistakes

  • Do not use inclusive right bounds with this half-open formula.
  • Do not query a prefix table after the source data changes.
  • Do not assume prefix totals are increasing when adjustments can be negative.

Connected lessons

Disjoint sparse tables: immutable sums with constant-time queries extends this range-query decision.

Two-dimensional prefixes: constant-time static rectangle sums extends this operation choice.

data structures
array-data-structure-guide
Storage details