Range Addition

Problem Overview

Given an array length and a list of range updates (each adding a delta to every element in an inclusive index range), return the final array after applying every update.

Why solve this?

The mirror image of prefix sums: instead of precomputing an array to answer range queries quickly, this precomputes a small set of edits to apply many range updates quickly, in O(1) per update instead of O(range length).

Pattern Recognition

Whenever many range updates each add the same delta across an inclusive range, and only the final array (not intermediate states) is needed, use a difference array — mark the start and end+1 of each range, then prefix-sum the difference array once at the end.

Prerequisites

• Running Sum of 1d Array — the closing prefix-sum step this technique's difference array is converted back with.

Hints

1. Applying each update by looping over its entire range costs O(range length) per update — with large ranges and many updates that's expensive.
2. Instead, record only the range's effect at its two boundaries: add delta at diff[start], and subtract delta at diff[end + 1] (if that index still exists).
3. After processing every update this way, a single prefix-sum pass over the difference array reconstructs the fully updated array.

Approach

Allocate a difference array of size length + 1, initialized to 0. For each update [start, end, delta]: add delta to diff[start] (every index from start onward should eventually include this delta), and subtract delta from diff[end + 1] if end + 1 is still within the difference array's bounds (this cancels the delta out for every index after the range ends). This records each range update in O(1), regardless of how wide the range is. After processing every update, reconstruct the final array with a single prefix-sum pass: result[0] = diff[0], and result[i] = result[i-1] + diff[i] for each subsequent index — the running sum of the difference array naturally re-expands every range update back into its full effect.

Code

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length + 1];
        for (int[] update : updates) {
            int start = update[0], end = update[1], delta = update[2];
            diff[start] += delta;
            if (end + 1 <= length) {
                diff[end + 1] -= delta;
            }
        }
        int[] result = new int[length];
        int running = 0;
        for (int i = 0; i < length; i++) {
            running += diff[i];
            result[i] = running;
        }
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy