Java segment tree: range sums with checked updates

The complete program targets Java 8. Compile it as one source file; its output is checked against the lesson.

Use one interval convention

A stock ledger needs the total quantity for a contiguous range of warehouse slots after individual corrections. This implementation uses half-open intervals: start is included and end is excluded. An empty range returns zero; a reversed or out-of-bounds range is rejected.

The tree uses an iterative layout with leaves starting at index n. It does not require n to be a power of two for this sum query. Parent values are rebuilt from child sums. Long storage prevents ordinary int-sum overflow for this bounded fixture, but arbitrary long inputs still need an overflow policy.

Update ownership is local

An update replaces one leaf rather than adding a delta, then recomputes its ancestors. A caller that mistakes replacement for increment will get plausible but incorrect totals. The test changes one warehouse from five to nine and checks the new sum.

This class is not thread-safe. A concurrent query can observe part of an update. Protect the complete tree operation with a lock or choose a versioned structure when readers need a consistent snapshot; marking the array reference volatile does not make its element mutations atomic as a group.

Working program

public class WarehouseRangeTotals {
    private final int size; private final long[] tree;
    WarehouseRangeTotals(int[] quantities) {
        size = quantities.length;
        if (size == 0 || size > 1000000) throw new IllegalArgumentException("size");
        tree = new long[2 * size];
        for (int index = 0; index < size; index++) tree[size + index] = quantities[index];
        for (int node = size - 1; node > 0; node--) tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    void replace(int index, int value) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        int node = index + size; tree[node] = value;
        while ((node /= 2) > 0) tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    long sum(int start, int end) {
        if (start < 0 || end < start || end > size) throw new IndexOutOfBoundsException();
        long total = 0;
        for (int left = start + size, right = end + size; left < right; left /= 2, right /= 2) {
            if ((left & 1) != 0) total += tree[left++];
            if ((right & 1) != 0) total += tree[--right];
        }
        return total;
    }
    public static void main(String[] args) {
        WarehouseRangeTotals stock = new WarehouseRangeTotals(new int[]{3, 5, 2, 7, 4});
        System.out.println(stock.sum(1, 4));
        stock.replace(1, 9); System.out.println(stock.sum(1, 4));
        System.out.println(stock.sum(2, 2));
        try { stock.sum(4, 2); } catch (IndexOutOfBoundsException rejected) { System.out.println("range rejected"); }
    }
}

Output

14
18
0
range rejected

Costs and boundaries

Construction is O(n), queries and point replacements are O(log n), and the array stores 2n long values. This version supports sums and point replacement only; lazy range updates need different state and are not implemented here.

Common Mistakes

• Do not mix inclusive and half-open endpoints.
• Point replacement is not a delta update.
• Protect a whole mutation when concurrent snapshots matter.

Read next

Java Fenwick tree: point additions and half-open prefix sums, Java arrays and bounds, Java multi-map invariants: one lock for a reservation boundary.

Extend this boundary

Continue with Java lazy segment tree: add to ranges and query sums.