Efficient Range Updates Using Difference Array

A difference array (sometimes called an Imos-style array) lets you record many range additions by writing only at boundaries. After all marks, one prefix pass materializes the final values in O(n) time.

Why this shows up in the real world

Picture a highway delay map: each night several contiguous segments gain +1 minute. Painting every kilometer is slow; instead you place +1 at the first affected marker and -1 just after the last—then a running total shows delay everywhere. Weekend hotel pricing, hourly ad impression buckets, and classroom seat “reserved” flags all use the same range mark → prefix to expand idea.

Core idea (explained for students)

Allocate diff of length n (or n+1 with a sentinel if you always write R+1). For “add v to inclusive indices [L,R]”, execute diff[L] += v and, if R + 1 < n, also diff[R + 1] -= v. After processing every update, compute running += diff[i] for i from 0 to n-1; that running array is your answer. 2D difference grids extend the same boundary idea to rectangles.

Try this in Python

def apply_range_adds(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """updates: (L, R, v) inclusive, 0-based indices"""
    diff = [0] * (n + 1)
    for L, R, v in updates:
        diff[L] += v
        diff[R + 1] -= v
    out, s = [], 0
    for i in range(n):
        s += diff[i]
        out.append(s)
    return out


# +5 on [1..3], +2 on [2..4] over indices 0..5
print(apply_range_adds(6, [(1, 3, 5), (2, 4, 2)]))

Common mistakes

• Forgetting - at R+1 when it exists—ranges “leak” forever to the right.
• Mixing 0-based vs 1-based indexing with the problem statement.
• Using this pattern when you must answer live point queries between updates without rebuilding—reach for a Fenwick tree or segment tree instead.

Key takeaways

• O(1) marker per range, O(n) finalize.
• Difference + prefix is a standard pair—draw spikes on a line before coding.
• Great when updates are offline or batched.