Java difference arrays: batch inclusive range additions

Mark where a change begins and ends

Adding four to positions one through three writes +4 at one and -4 after three. A second update subtracts one from positions two through four. The final scan gives [0, 4, 3, 3, -1]. The test also rejects an inverted interval before changing any boundary.

The add operation is fast because it postpones materialization. Reading one final value before reconstruction would be wrong. For interleaved online updates and reads, lazy segment trees or other indexed structures fit better.

Know the endpoint convention

This page uses inclusive [left, right]. Prefix-sum queries use half-open [start, end). Name that difference at the API boundary; an off-by-one update near the last element is easy to miss.

Working program

import java.util.Arrays;
public class ReceiptRangeAdjustments {
    static void add(long[] difference, int left, int right, long delta) {
        if (left < 0 || right < left || right >= difference.length) throw new IndexOutOfBoundsException();
        difference[left] = Math.addExact(difference[left], delta);
        if (right + 1 < difference.length)
            difference[right + 1] = Math.subtractExact(difference[right + 1], delta);
    }
    public static void main(String[] args) {
        long[] difference = new long[5];
        add(difference, 1, 3, 4);
        add(difference, 2, 4, -1);
        try { add(difference, 4, 2, 9); }
        catch (IndexOutOfBoundsException rejected) { System.out.println("bad interval"); }
        long[] values = new long[difference.length];
        long total = 0;
        for (int index = 0; index < values.length; index++) {
            total = Math.addExact(total, difference[index]);
            values[index] = total;
        }
        System.out.println(Arrays.toString(values));
    }
}

Output

bad interval
[0, 4, 3, 3, -1]

Costs and boundaries

For k validated updates and n final values, this takes O(k+n) time and O(n) difference storage. The two boundary writes are not an atomic transaction if arithmetic or surrounding application work fails partway through.

Common Mistakes

• Do not read a point from the unmaterialized difference array as a final value.
• Do not silently mix inclusive and half-open endpoints.
• Do not call two boundary writes a transactional update.

Read next

Java prefix sums: answer repeated half-open range totals, Java Fenwick tree: point additions and half-open prefix sums, Java lazy segment tree: add to ranges and query sums.