Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Difference Array
DSA

Difference Array

Learn how difference arrays efficiently handle multiple range update operations.

A Difference Array efficiently handles repeated range updates.

Instead of updating every element in a range, mark only where the change starts and ends:

Range update → Mark boundaries → Prefix sum → Get final array

Focus on recognizing:

Many range updates + final array → Difference Array

Core Template

Watch [1,3]+=5 and [2,4]+=2 land as four boundary writes on the diff array, then one sweep reconstructs [0,5,7,7,2,0]. Press ▶ to animate.

Difference Array (Range Add in O(1))

Apply many range-add updates in O(1) each, then reconstruct the final array in one O(n) sweep. For example, given n = ${state.n}, apply [1,3]+=5 and [2,4]+=2. Instead of touching every cell in a range, write +x at the start and -x just past the end; a prefix sum then spreads the change across the range. The final array is [${state.result}].

n=6, diff has n+1 cells so r+1 is always safe. Update [1,3]+=5 → diff[1]+=5, diff[4]-=5. Update [2,4]+=2 → diff[2]+=5... watch the diff array fill with +5/-5/+2/-2 at the boundaries. Then a running sum sweeps left to right to produce the result [0,5,7,7,2,0].

ARRAY VISUALIZER
Steps –
0
0
0
1
0
2
0
3
0
4
0
5
0
6
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        diff[l] += x; diff[r+1] -= x   (per update)
                      
                        2
                        apply update [1,3] += 5
                      
                        3
                        apply update [2,4] += 2
                      
                        4
                        current = 0; for i in 0..n-1:
                      
                        5
                          current += diff[i]; result[i] = current
                      
public int[] rangeUpdates(int n, int[][] updates) {
    int[] diff = new int[n + 1];

    for (int[] update : updates) {
        int l = update[0];
        int r = update[1];
        int x = update[2];

        diff[l] += x;
        diff[r + 1] -= x;
    }

    int[] result = new int[n];
    int current = 0;

    for (int i = 0; i < n; i++) {
        current += diff[i];
        result[i] = current;
    }

    return result;
}
def range_updates(n, updates):
    diff = [0] * (n + 1)

    for l, r, x in updates:
        diff[l] += x
        diff[r + 1] -= x

    result = []
    current = 0

    for i in range(n):
        current += diff[i]
        result.append(current)

    return result
vector<int> rangeUpdates(int n, vector<vector<int>>& updates) {
    vector<int> diff(n + 1, 0);

    for (auto& u : updates) {
        int l = u[0], r = u[1], x = u[2];
        diff[l] += x;
        diff[r + 1] -= x;
    }

    vector<int> result(n);
    int current = 0;

    for (int i = 0; i < n; i++) {
        current += diff[i];
        result[i] = current;
    }

    return result;
}
function rangeUpdates(n, updates) {
  const diff = Array(n + 1).fill(0);

  for (const [l, r, x] of updates) {
    diff[l] += x;
    diff[r + 1] -= x;
  }

  const result = [];
  let current = 0;

  for (let i = 0; i < n; i++) {
    current += diff[i];
    result.push(current);
  }

  return result;
}

diff[l] += x starts the change · diff[r+1] -= x stops it. Each update is O(1).

Why It Works

The prefix sum propagates each boundary mark across the array:

Original: [2, 2, 2, 2]        Add +3 to [1, 2]

Diff:     [0, 3, 0, -3]
Sweep:     0 → 3 → 3 → 0
Result:   [2, 5, 5, 2]

Difference Array is Prefix Sum run in reverse: updates become marks, marks become values.

Common Mistakes

Forgetting r + 1.

diff[r] -= x kills the change one index early — it must survive through index r.

Array too small.

Size n + 1 keeps diff[r + 1] safe when r == n - 1.

Skipping the sweep.

The diff array stores only changes — current += diff[i] is what turns them into final values.

Complexity

PhaseTime
q updatesO(q)
Final sweepO(n)
vs naive O(n·q)—

My Private Notes

Notes are auto-saved locally to this device.