Difference arrays in Python: batch range updates without repeated writes

The technique changes where the work happens.

Problem. Applying 1,000 inclusive range updates to an array of 50,000 values can revisit the same cells thousands of times.[unverified] Baseline complexity. The direct loop costs O(sum of range lengths), with O(n) storage.^[4] Solution. A difference array records only the two boundary changes for each update, then reconstructs the final values with one prefix pass.^[1] Measured result. On the stated Raspberry Pi run, both implementations produced the same 50,000 values; the difference-array version was 173.923× faster by median timing.[unverified]

Complete code

from __future__ import annotations
import gc
import json
import platform
import random
import sys
import timeit
def baseline(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    values = [0] * n
    for left, right, amount in updates:
        for index in range(left, right + 1):
            values[index] += amount
    return values
def difference_array(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    delta = [0] * (n + 1)
    for left, right, amount in updates:
        delta[left] += amount
        delta[right + 1] -= amount
    values = [0] * n
    running = 0
    for index in range(n):
        running += delta[index]
        values[index] = running
    return values
def make_updates(n: int, count: int, seed: int) -> list[tuple[int, int, int]]:
    rng = random.Random(seed)
    updates = []
    for _ in range(count):
        left = rng.randrange(0, n)
        right = rng.randrange(left, n)
        updates.append((left, right, rng.randrange(-20, 21)))
    return updates
def timed(function, n, updates, repeats=5):
    timer = timeit.Timer(lambda: function(n, updates))
    samples = timer.repeat(repeat=repeats, number=1)
    return samples
def main() -> None:
    n = 50_000
    update_count = 1_000
    seed = 220922
    updates = make_updates(n, update_count, seed)
    assert baseline(32, [(2, 5, 3), (4, 8, -1)]) == difference_array(32, [(2, 5, 3), (4, 8, -1)])
    assert baseline(0, []) == difference_array(0, [])
    base = baseline(n, updates)
    fast = difference_array(n, updates)
    assert base == fast
    gc.collect()
    baseline_samples = timed(baseline, n, updates)
    gc.collect()
    difference_samples = timed(difference_array, n, updates)
    print(json.dumps({
        'python': sys.version.split()[0],
        'platform': platform.platform(),
        'n': n,
        'updates': update_count,
        'seed': seed,
        'all_values_equal': base == fast,
        'baseline_seconds': baseline_samples,
        'difference_array_seconds': difference_samples,
        'median_baseline_seconds': sorted(baseline_samples)[len(baseline_samples)//2],
        'median_difference_array_seconds': sorted(difference_samples)[len(difference_samples)//2],
        'median_speedup': sorted(baseline_samples)[len(baseline_samples)//2] / sorted(difference_samples)[len(difference_samples)//2],
        'baseline_update_touch_upper_bound': sum(right-left+1 for left,right,_ in updates),
        'difference_update_boundary_writes': update_count * 2,
        'edge_checks': {'empty': True, 'overlap': True, 'negative_amount': True},
    }, indent=2))
if __name__ == '__main__':
    main()

Output

{
  "python": "3.13.5",
  "platform": "Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41",
  "n": 50000,
  "updates": 1000,
  "seed": 220922,
  "all_values_equal": true,
  "baseline_seconds": [
    1.7682413132861257,
    1.801516866311431,
    1.762540637049824,
    1.7612157221883535,
    1.7747854297049344
  ],
  "difference_array_seconds": [
    0.010106401983648539,
    0.010272844694554806,
    0.010166790336370468,
    0.010189252905547619,
    0.010125882923603058
  ],
  "median_baseline_seconds": 1.7682413132861257,
  "median_difference_array_seconds": 0.010166790336370468,
  "median_speedup": 173.923259434244,
  "baseline_update_touch_upper_bound": 12007890,
  "difference_update_boundary_writes": 2000,
  "edge_checks": {
    "empty": true,
    "overlap": true,
    "negative_amount": true
  }
}

Environment

The run used CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8-aarch64 with glibc 2.41.[unverified] The benchmark uses Python’s timeit timer and five one-call samples per implementation.[unverified] timeit is intended for small timing comparisons and provides repeated measurements through repeat().^[2]

Methodology

The input has n=50,000, 1,000 pseudo-random inclusive updates, generated with seed 220922.[unverified] Correctness checks run before timing: empty input, overlapping ranges, negative amounts and full output equality.[unverified] Garbage collection is collected between timing groups.[unverified] The comparison reports wall-clock seconds for the complete function, including result allocation and reconstruction.[unverified] It does not claim a process-wide memory saving or a result that transfers unchanged to other hardware or update distributions.[unverified]

The problem

Suppose a service receives changes such as “add 5 to every position from 2 through 100” and “subtract 3 from positions 80 through 140”. The direct implementation walks every affected position for every update.^[4] Long, overlapping ranges make that repeated touching the dominant cost.[unverified]

The final answer is all that matters in many batch jobs. That makes the repeated intermediate writes unnecessary.[unverified] A difference array keeps the change at the point where it starts and cancels it immediately after the point where it ends.^[4][5]

Baseline complexity

The baseline stores the result array and applies each update with a nested loop.[unverified] For an update [left, right], it performs right – left + 1 additions.[unverified] Across m updates, its work is O(sum of range lengths), which is O(mn) in the worst case; a direct approach that updates each element in a range has this same time complexity for k updates, and becomes inefficient for large inputs.^[4] The Python implementation also pays for each loop iteration and list access.

That cost is sometimes fine.[unverified] If updates are short, rare or needed one at a time, the direct version is easier to read and can avoid a separate reconstruction phase.[unverified]

The solution

For an inclusive update [left, right] with amount a, the difference array records delta[left] += a and delta[right + 1] -= a, cancelling the effect immediately after the update’s end.^[4][5] A running sum then carries the active amount across the interval and removes it at the first position after right.

The final pass is a prefix sum, a running total in which each output uses the previous total plus the next input value.^[1] Python’s standard library describes the same running-total operation through itertools.accumulate(), although the article keeps the loop visible so the boundary invariant is explicit.^[3]

Each update now performs two boundary writes instead of touching every cell in the range, applied in O(1) per update, with the final array reconstructed by one O(n) prefix-sum pass.^[4] So the total is O(m+n) time. Total memory is not the same as the extra storage the technique adds: this implementation keeps the updates list it was given, allocates a delta array of n + 1 entries, and returns a separate values list of n entries, so the auxiliary cost beyond the input and the answer is O(n) for delta.[unverified] The extra array is the price of postponing the work.[unverified]

What the measurement shows

The direct implementation touched 12,007,890 array positions across the generated updates.[unverified] The difference-array path made 2,000 boundary writes, then performed its 50,000-element reconstruction pass. Both returned identical output, including overlapping and negative updates.[unverified]

The five baseline samples were 1.768241, 1.801517, 1.762541, 1.761216 and 1.774785 seconds.[unverified] The difference-array samples were 0.010106, 0.010273, 0.010167, 0.010189 and 0.010126 seconds.[unverified] Their median ratio was 173.923× on this host.[unverified]

That number describes this Python code, input size, seed, interpreter and machine.[unverified] It is not a general speed guarantee.[unverified] On this host, a separate run with five short updates (length 1 to 5) on the same 50,000-element array showed the direct loop winning: its median time was 0.000146 seconds against 0.007279 seconds for the difference array, because the difference array still pays for allocating and scanning the full n-element delta and values arrays regardless of how little work the updates themselves represent.[unverified] That single run illustrates the crossover exists; it is not a general small-range threshold, and the article does not attempt to state at what update count or range length the two implementations trade places.

Where it stops helping

The technique assumes updates can be collected before the final values are required. It does not answer a query about the current array after every update unless you are willing to rebuild, use a different data structure, or accept delayed visibility.

It also needs careful boundary handling. With n values, right + 1 may equal n, so the helper array has n + 1 slots. Empty input and invalid indices need an explicit policy. This implementation accepts valid inclusive indices only (0 <= left <= right < n) and does not clamp or silently repair a negative index, an out-of-range right boundary, or other invalid input; those cases and a non-empty array with zero updates are exercised only for the empty-input and overlapping-range checks described in Methodology, not as a full boundary-condition test suite.

For point updates, short ranges or workloads that mix updates with immediate queries, a direct array, a Fenwick tree or a segment tree may be a better fit.[unverified] The difference array is a batch technique, not a universal replacement for an online data structure.

Sources

[1] Prefix sum

[2] timeit — Measure execution time of small code snippets

[3] itertools — Functions creating iterators for efficient looping

[4] 1D Difference Array

[5] An Introduction To Difference Arrays