Lesson 5.3 · Prefix Sum

Difference Arrays for Range Updates

The reverse of a prefix sum: mark +v at the start of a range and −v after its end, then one prefix sum applies every update.

10 min

Think of it like this

A guesthouse register: when a group of 3 arrives on day 2 and leaves after day 5, write "+3" on day 2 and "−3" on day 6. At the end, a running total down the calendar gives the number of guests every day.

1.Marking ranges

To add v to every element in [l, r], do diff[l] += v and diff[r + 1] -= v. Each update is O(1) regardless of the range length. After all updates, the prefix sum of diff is the final array.

Difference.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int n = 6;
        int[] diff = new int[n + 1];
        int[][] updates = {{1, 3, 2}, {2, 5, 3}};     // add 2 to [1..3], add 3 to [2..5]
        for (int[] u : updates) {
            diff[u[0]] += u[2];
            diff[u[1] + 1] -= u[2];
        }
        int[] result = new int[n];
        int running = 0;
        for (int i = 0; i < n; i++) { running += diff[i]; result[i] = running; }
        System.out.println(Arrays.toString(result));
    }
}

Output

[0, 2, 5, 5, 3, 3]

Remember

Range add = two point updates on the difference array.
One prefix sum at the end produces the final values.
O(n + updates) total.

Common mistakes

Making diff length n and writing to diff[r + 1] when r is the last index (use length n + 1).
Reading values before taking the final prefix sum.

Command Palette

Difference Arrays for Range Updates

1.Marking ranges