Data Structures & Algorithms / Contracts, sequences, and search / Lesson 2

Arrays, prefix sums, and range contracts

Use half-open intervals to preprocess repeated sum queries and distinguish static queries from range updates.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Choose an interval convention and keep it
Build prefix sums with one extra position
Preprocessing pays off only for the right workload

Choose an interval convention and keep it

A half-open interval [left,right) includes left and excludes right. Its length is right-left, an empty interval has equal endpoints, and adjacent intervals meet without overlap. This convention matches Python slicing and range iteration, making boundary reasoning consistent. Validate 0 <= left <= right <= n at a public query boundary. Negative Python indices are legitimate language features but may violate your algorithm’s intended domain. Do not let accidental negative indexing turn an invalid range into a plausible result. Write the interval contract beside every preprocessing formula.

Build prefix sums with one extra position

Define prefix[k] as the sum of elements strictly before position k. Then prefix[0] is zero and prefix[n] is the whole sum. Subtracting prefix[left] from prefix[right] removes exactly the part before the desired interval. The first example therefore answers each valid static query with two array accesses and a subtraction after linear preprocessing and linear additional storage. Negative values do not break this identity. The arithmetic model assumes bounded-cost addition for analysis; Python’s arbitrary-size integers can require bit-length accounting for unusually large values.

python Self-contained Python3 algorithm example using synthetic local data.

def prefix_sums(values):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix, left, right):
    n = len(prefix) - 1
    if not 0 <= left <= right <= n:
        raise ValueError("Invalid half-open range")
    return prefix[right] - prefix[left]

prefix = prefix_sums([4, -2, 5, 1])
print(prefix)
print(range_sum(prefix, 1, 3))
print(range_sum(prefix, 2, 2))

Expected output

[0, 4, 2, 7, 8]
3
0

The query [1,3) includes -2 and 5. Equal endpoints select no values and yield zero.

Preprocessing pays off only for the right workload

One sum over an array can be computed directly in linear time without storing all prefixes. Prefix sums become useful when many range queries share an unchanged snapshot: preprocessing O(n) plus q constant-time queries replaces repeatedly scanning ranges. If a value changes, all later prefixes may change, so the original structure no longer answers current queries correctly. Rebuilding after every update can dominate the workload. Later tree structures address dynamic queries; do not advertise static prefix sums as constant-time updates merely because their query formula is short.

Use differences for a batch of range additions

A difference array records where a running contribution starts and stops. To add delta over [left,right), add delta at left and subtract it at right, then recover values by a prefix scan. The second example applies several updates before reading any final values. An n+1 difference array makes a stop at right=n representable without a special missing slot. This is a batch technique, not a dynamic arbitrary range-sum index. Its contract assumes additive updates and one reconstruction; mixing it with unrelated overwrites requires a new model and proof.

python Self-contained Python3 algorithm example using synthetic local data.

def apply_additions(n, updates):
    diff = [0] * (n + 1)
    for left, right, delta in updates:
        if not 0 <= left <= right <= n:
            raise ValueError("Invalid half-open range")
        diff[left] += delta
        diff[right] -= delta
    result = []
    running = 0
    for index in range(n):
        running += diff[index]
        result.append(running)
    return result

print(apply_additions(5, [(1, 4, 3), (2, 5, -1)]))

Expected output

[0, 3, 2, 2, -1]

The second update overlaps positions 2 and 3 and extends through position 4. The stop at 5 is recorded but not emitted.

Distinguish a copy from a shared input snapshot

A prefix array is derived from specific values at a particular point. If another component mutates the original list, the old prefix values do not magically update. Document ownership or take an accepted snapshot before preprocessing. A shallow list copy protects element membership but not mutable objects stored inside it. For numeric arrays this is usually straightforward; for records, select the relevant immutable numeric field. Avoid using a cached prefix array merely because the current list has the same length. Content, units, and ordering are dependencies too.

Check every boundary against a simple oracle

For a small array, enumerate all valid pairs left <= right and compare range_sum with Python’s direct sum over the slice. Include empty input, all-zero values, negative values, the full interval, and singleton intervals. For batch additions, compare with a simple nested loop that updates every affected position on tiny fixtures. Those reference implementations may be slower but are easier to trust as differential checks. Keep invalid-range tests separate so rejection is intentional rather than an incidental IndexError. Finite exhaustive fixtures complement the algebraic prefix identity rather than replacing it.

Common errors and fixes

The rightmost value is included twice

Why it happens: Inclusive and half-open endpoints were mixed.
How to fix it: Use one convention and derive length and subtraction from it.
Prevent it next time: Test empty and singleton intervals.

Queries stay unchanged after source mutation

Why it happens: Preprocessing belongs to an older snapshot.
How to fix it: Rebuild or select an appropriate dynamic data structure.
Prevent it next time: Track data version and every relevant dependency.

A range ending at n overruns the difference array

Why it happens: No sentinel stop position was allocated.
How to fix it: Use n+1 difference entries and emit only n values.
Prevent it next time: Include full-range and final-position updates.

Check your understanding

1. What is the sum of [0,4) in the first fixture and why?

Show worked solution

prefix[4]-prefix[0] is 8-0=8, covering 4,-2,5,1 exactly once. The extra zero makes the full-range formula identical to interior queries. There is no need for a separate left-is-zero branch.

2. Why should a zero-length update add and subtract at the same position?