Range Addition

medium difference array prefix sum

Problem

Apply k range updates of the form [start, end, val] to a length-n array initialized to 0; return the final array.

Inputlength = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]

Output[-2,0,3,5,3]

Each update is O(1) into a difference array; one prefix sum produces the result.

length

updates (s,e,v ;)

def get_modified_array(length, updates):
    diff = [0]*(length + 1)
    for s, e, v in updates:
        diff[s] += v
        diff[e + 1] -= v
    out = []
    cur = 0
    for i in range(length):
        cur += diff[i]
        out.append(cur)
    return out

function getModifiedArray(length, updates) {
  const diff = new Array(length + 1).fill(0);
  for (const [s, e, v] of updates) { diff[s] += v; diff[e + 1] -= v; }
  const out = []; let cur = 0;
  for (let i = 0; i < length; i++) { cur += diff[i]; out.push(cur); }
  return out;
}

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length + 1];
        for (int[] u : updates) { diff[u[0]] += u[2]; diff[u[1] + 1] -= u[2]; }
        int[] out = new int[length]; int cur = 0;
        for (int i = 0; i < length; i++) { cur += diff[i]; out[i] = cur; }
        return out;
    }
}

vector getModifiedArray(int length, vector>& updates) {
    vector diff(length + 1, 0);
    for (auto& u : updates) { diff[u[0]] += u[2]; diff[u[1] + 1] -= u[2]; }
    vector out(length, 0); int cur = 0;
    for (int i = 0; i < length; i++) { cur += diff[i]; out[i] = cur; }
    return out;
}

Explanation

The slow way to apply many range updates is to loop over every index in [start, end] and add val each time. The clever trick here is the difference array: instead of touching the whole range, we only mark its two ends and rebuild the answer with one prefix sum at the very end.

For each update [s, e, v] we do diff[s] += v and diff[e+1] -= v. The first mark says "from here on, add v"; the second mark cancels it right after the range ends. Each update is therefore just two operations, no matter how wide the range is.

Once all updates are recorded, we sweep left to right keeping a running total cur. At index i, cur += diff[i] gives exactly the net of all the "turn on" and "turn off" marks that apply there, which is the final value.

Example: length = 5, update [1,3,2] sets diff[1] += 2 and diff[4] -= 2. Sweeping, indices 1, 2, 3 each pick up +2, while index 4 gets the -2 back, so the bump only covers positions 1 through 3 — exactly the range we wanted.

Because every update is O(1) and the final sweep is one pass, the whole thing runs in O(n + k) instead of O(n·k).

Time: O(n + k) Space: O(n)