Difference array

O(n)

Record range updates as two point edits, add val at the start, subtract it just after the end, and only turn that into real values with one final prefix-sum pass, instead of touching every element on every update.

Signals

many range updates first, then read the final array onceadd a value to every element in a range, repeated many timesapply k range increments before answering any querybooking/interval counters over an array

Template

function applyRangeUpdates(n, updates) {
    const diff = new Array(n + 1).fill(0);
    for (const [l, r, val] of updates) {
        diff[l] += val;
        diff[r + 1] -= val;
    }
    const result = new Array(n);
    let running = 0;
    for (let i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}

Looks similar, isn't

Prefix sums: Prefix sums are for many range READS on a fixed array. A difference array is for the opposite order of work: many range UPDATES applied first, with the array only materialized once at the end.

n up to 1e5..1e6 with q range updates -> O(n + q): each update is two O(1) point edits, and one final O(n) prefix-sum pass reconstructs the array, instead of O(n) per update.

Learn this pattern