Module 06 · Prefix Sums, Prefix State, and Difference Arrays

058. Range Addition with Difference Array

Interview · Download this solution · All solutions and shared helpers

Problem

Start with n zeros and apply updates (left,right,delta), adding delta to every index in [left,right). Bounds satisfy 0<=left<=right<=n. Return the final array. Empty updates and empty ranges are valid; n may be zero.

Examples

Example 1

range_additions(5, [(1, 4, 2)])
=> [0, 2, 2, 2, 0]

The exclusive right boundary turns the update off.

Example 2

range_additions(3, [(0, 3, 2), (1, 2, -1)])
=> [2, 1, 2]

Overlapping positive and negative updates add.

Example 3

range_additions(0, [])
=> []

There are boundaries but no cells to emit.

Reveal the worked solution and reasoning

Why this mechanism works

A range addition changes the running adjustment only at its two boundaries: turn delta on at left and off at right. Record these changes in a difference array, then integrate them with a prefix sum. Overlapping updates combine by addition automatically.

State and boundaries

difference stores changes in active adjustment at boundaries. active is the adjustment applying to the current output cell.

Protocol

Allocate n+1 boundary differences.
Add delta at left and subtract it at right.
Scan the first n boundaries with a running sum.
Emit active for each cell.

Visualization

add 2 on [1,4)
difference: 0,+2,0,0,-2,0
integrate:  0, 2,2,2, 0

Python implementation

def range_additions(n, updates):
    difference = [0] * (n + 1)
    for left, right, delta in updates:
        difference[left] += delta
        difference[right] -= delta
    output = []
    active = 0
    for i in range(n):
        active += difference[i]
        output.append(active)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

range_additions(5, [(1, 4, 2)])

L2 range_additions: difference = [0] * (n + 1)
n=5; updates=[(1, 4, 2)]; difference=[0, 0, 0, 0, 0, 0]

L3 range_additions: for left, right, delta in updates:
n=5; updates=[(1, 4, 2)]; difference=[0, 0, 0, 0, 0, 0]; left=1; right=4; delta=2

L4 range_additions: difference[left] += delta
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, 0, 0]; left=1; right=4; delta=2

L5 range_additions: difference[right] -= delta
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2

L6 range_additions: output = []
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[]

L7 range_additions: active = 0
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[]; active=0

L8 range_additions: for i in range(n):
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[]; active=0; i=0

L10 range_additions: output.append(active)
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[0]; active=0; i=0

... 6 intermediate state changes omitted ...

L10 range_additions: output.append(active)
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[0, 2, 2, 2]; active=2; i=3

L8 range_additions: for i in range(n):
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[0, 2, 2, 2]; active=2; i=4

L9 range_additions: active += difference[i]
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[0, 2, 2, 2]; active=0; i=4

L10 range_additions: output.append(active)
n=5; updates=[(1, 4, 2)]; difference=[0, 2, 0, 0, -2, 0]; left=1; right=4; delta=2; output=[0, 2, 2, 2, 0]; active=0; i=4

Result: [0, 2, 2, 2, 0]. The exclusive right boundary turns the update off.

range_additions(3, [(0, 3, 2), (1, 2, -1)])

L2 range_additions: difference = [0] * (n + 1)
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[0, 0, 0, 0]

L3 range_additions: for left, right, delta in updates:
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[0, 0, 0, 0]; left=0; right=3; delta=2

L4 range_additions: difference[left] += delta
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, 0, 0, 0]; left=0; right=3; delta=2

L5 range_additions: difference[right] -= delta
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, 0, 0, -2]; left=0; right=3; delta=2

L3 range_additions: for left, right, delta in updates:
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, 0, 0, -2]; left=1; right=2; delta=-1

L4 range_additions: difference[left] += delta
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 0, -2]; left=1; right=2; delta=-1

L5 range_additions: difference[right] -= delta
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 1, -2]; left=1; right=2; delta=-1

L6 range_additions: output = []
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 1, -2]; left=1; right=2; delta=-1; output=[]

... 6 intermediate state changes omitted ...

L10 range_additions: output.append(active)
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 1, -2]; left=1; right=2; delta=-1; output=[2, 1]; active=1; i=1

L8 range_additions: for i in range(n):
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 1, -2]; left=1; right=2; delta=-1; output=[2, 1]; active=1; i=2

L9 range_additions: active += difference[i]
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 1, -2]; left=1; right=2; delta=-1; output=[2, 1]; active=2; i=2

L10 range_additions: output.append(active)
n=3; updates=[(0, 3, 2), (1, 2, -1)]; difference=[2, -1, 1, -2]; left=1; right=2; delta=-1; output=[2, 1, 2]; active=2; i=2

Result: [2, 1, 2]. Overlapping positive and negative updates add.

Why the solution is correct

An update contributes delta to the prefix of differences exactly from left through right-1; at right its opposite delta cancels it. Summing contributions over updates therefore gives the required final value at every cell.

Time and space

O(n+q) time and O(n) storage for n cells and q updates.

Common mistakes

Subtracting at right-1 ends the update one cell early. The extra boundary n is needed for updates reaching the array's end.

Reasoning card

State: difference stores changes in active adjustment at boundaries. active is the adjustment applying to the current output cell.

Invariant: Running difference sum equals active range updates.

Decision to rehearse: Record changes at boundaries, then prefix-sum.

Finish: Emit active for each cell

Transfer exercise

Recover a difference array from an existing nonzero array, then apply the same update protocol.