Java prefix sums: answer repeated half-open range totals

Define the boundary before coding

The first prefix slot is zero. After processing n numbers, prefix has n+1 slots, which makes an empty range legal and avoids a special case at index zero. The program asks for indices one through three, excluding index three. It also checks an empty range, whose total is zero.

Negative values are fine; a sliding-window rule that assumes nonnegative values would not be interchangeable. Sliding windows answer a different set of questions. Use a long accumulator when int values may add up beyond int range, and define what to do if even long overflows.

Updates invalidate the snapshot

This structure is for many reads over values that remain fixed. Changing a source element makes later prefix totals stale. Fenwick trees cover point updates with prefix queries, while difference arrays handle a batch of range additions before a final read.

Working program

public class ReceiptPrefixTotals {
    static long range(long[] prefix, int start, int end) {
        if (start < 0 || end < start || end >= prefix.length) throw new IndexOutOfBoundsException();
        return prefix[end] - prefix[start];
    }
    public static void main(String[] args) {
        int[] changes = {4, -2, 7, 1};
        long[] prefix = new long[changes.length + 1];
        for (int index = 0; index < changes.length; index++)
            prefix[index + 1] = Math.addExact(prefix[index], changes[index]);
        System.out.println("range=" + range(prefix, 1, 3));
        System.out.println("empty=" + range(prefix, 2, 2));
    }
}

Output

range=5
empty=0

Costs and boundaries

Building the array takes O(n) time and O(n) additional space; each validated range query takes O(1). The subtraction can still overflow long for arbitrary external data, so a larger numeric policy may be needed.

Common Mistakes

• Do not mix inclusive and half-open endpoints.
• Do not mutate the source after building prefixes and use stale totals.
• Do not sum large int batches in an int accumulator.

Read next

Java sliding windows: fixed-size range totals, Java Fenwick tree: point additions and half-open prefix sums, Java arrays and bounds.