Difference arrays and interval clamping

A difference arraydifference arrayAn array storing the differences between consecutive elements, used to apply multiple range updates in O(1) time per update.In the glossary is the inverse of a prefix sum. Instead of storing cumulative totals, it stores the changes between consecutive elements. When you apply a prefix sum to a difference array, you get back the original array with all range updates applied.

The difference array technique

Suppose you want to add 5 to every element in the range [1, 3] of an array of zeros.

arr = [0, 0, 0, 0, 0]

You could loop through indices 1 to 3 and add 5 to each. But if you have many such updates, looping is slow. A difference array handles this in O(1) time.

A difference array diff records changes:

diff = [0, 5, 0, 0, -5, 0]

Here, diff[1] = 5 means "add 5 starting at index 1". diff[4] = -5 means "stop adding 5 after index 3" (or equivalently, subtract 5 starting at index 4).

To reconstruct the array from the difference array, compute a prefix sum:

1diff = [0, 5, 0, 0, -5, 0]2arr = [0]3for i in range(1, len(diff)):4    arr.append(arr[-1] + diff[i])5print(arr)

The output is:

[0, 5, 5, 5, 0, 0]

Follow the running total: starting from 0, diff[1] = 5 takes it to 5, diff[2] and diff[3] are both 0 so it stays at 5, and diff[4] = -5 brings it back down to 0. Indices 1, 2 and 3 all read 5, which is exactly the range [1, 3] you set out to update. The array has six entries because diff does, but only the first five, indices 0 through 4, belong to the original array. The sixth entry is the stop marker's own running total, and you drop it once the prefix sum is done.

Implementation details

When building a difference array, always allocate it with size n+1, where n is the size of the original array. The extra element at the end ensures that range updates do not go out of bounds.

To apply an update that adds val to indices [l, r] (inclusive), do:

• diff[l] += val (start the increase at index l)
• diff[r + 1] -= val (stop the increase after index r)

Getting the stop index right, r + 1 rather than r, is the one detail worth double-checking every time you write this pattern.

Applying multiple updates

The power of difference arrays is handling many updates together. Each update is O(1):

1n = 52diff = [0] * (n + 1)3
4# Add 3 to range [0, 2]5diff[0] += 36diff[3] -= 37
8# Add 2 to range [1, 4]9diff[1] += 210diff[5] -= 211
12# Reconstruct the array13arr = [0]14for i in range(1, n + 1):15    arr.append(arr[-1] + diff[i])16print(arr[1:])  # Skip the leading 0

The output is:

[3, 5, 5, 2, 2]

The first three elements get +3. Elements 1 and 2 additionally get +2. Elements 3 and 4 get only +2. The difference array tracks all changes, then a single prefix sum applies them all.

A second example: turning on lights in a corridor

Imagine a corridor with 100 lights, all off. You have a sequence of commands: turn on lights from position i to position j. After all commands, count how many lights are on.

1n = 102diff = [0] * (n + 1)3
4# Turn on lights [0, 3], [2, 5], [4, 7]5ranges = [(0, 3), (2, 5), (4, 7)]6for l, r in ranges:7    diff[l] += 18    diff[r + 1] -= 19
10# Reconstruct to see which lights are on11lights_on = 012current = 013for i in range(n):14    current += diff[i]15    if current > 0:16        lights_on += 117
18print(f"Lights on: {lights_on}")

Each range update increments a region in the difference array. After all updates, a pass through the array counts how many lights overlap (how many ranges cover each position). This is much faster than looping through each range to mark each light individually.

Clamping a range to the array

A problem does not always guarantee that an update's range fits neatly inside the array. An update might ask you to add to indices [-2, 3] or [4, 1000] when the array only has 10 elements. Before you touch diff, clamp l up to 0 and clamp r down to n - 1: l = max(l, 0) and r = min(r, n - 1).

Clamping matters for a second reason beyond staying in bounds. If, after clamping, l ends up greater than r, the whole range falls outside the array, and the update does nothing: skip it rather than writing to diff at all. Applying diff[r + 1] -= val with a stale, unclamped r can also write past the end of the array you allocated, so clamp before you touch the difference array, not after.

Common mistakes with difference arrays

One error is forgetting the +1 in the stop index. To update range [l, r], you do diff[r + 1] -= val. Forgetting the +1 will affect index r+1 incorrectly.

Another mistake is not allocating the difference array with size n+1. The array must be one element longer than the original to hold the stop marker.

A third mistake is confusing when to apply the prefix sum. The difference array itself is not the answer; you must apply a prefix sum to reconstruct the final array. Querying the difference array directly gives the wrong result.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    n = int(input_data[0])10    m = int(input_data[1])11
12    diff = [0] * (n + 1)13
14    idx = 215    for _ in range(m):16        l = int(input_data[idx])17        r = int(input_data[idx + 1])18        val = int(input_data[idx + 2])19        diff[l] += val20        diff[r + 1] -= val21        idx += 322
23    # Reconstruct24    arr = []25    current = 026    for i in range(n):27        current += diff[i]28        arr.append(current)29
30    sys.stdout.write(" ".join(map(str, arr)) + "\n")31
32
33if __name__ == "__main__":34    main()

5 3
0 2 3
1 4 2
3 3 1

3 5 5 3 2

The program reads a series of range updates, applies them to a difference array, then reconstructs the final array in O(1) per update.

Building intuition

Think of a difference array as a recipe for building the final array. Instead of stating what each element is, you state the changes. diff[i] says "at position i, the value increases by this amount compared to position i-1". When you accumulate these changes from left to right, you reconstruct the original array.

This perspective makes it clear why the technique works: a range update becomes two point updates in the difference array (one to start the change, one to end it). After all updates, a single pass reconstructs the answer.

Common patterns

Difference arrays appear in problems about:

• Applying multiple range increments to an array.
• Tracking events that start and end at certain points.
• Scheduling problems where resources are allocated and deallocated.
• Interval problems where you need to know how many intervals cover each point.

Recognize the pattern: many updates to ranges, then you need to query the final values. Difference arrays are the answer.

Why it matters

Difference arrays are a small technique with a large payoff. Applying M range updates directly, one loop per update, costs O(M * N) in the worst case. Recording the same updates in a difference array and reconstructing once costs O(M + N). When a problem gives you a large array and many range updates, reach for this pattern.