fix: off-by-one bounds guards in SegmentTree - #7573

Problem

SegmentTree guards update and getSum against out-of-range positions, but both guards compare against n instead of n - 1. Valid positions are 0 .. n-1, so index == n slips past the check.

In update the guard is followed immediately by an array read, so the call throws from inside the very method that was supposed to reject it:

public void update(int index, int value) {
    if (index < 0 || index > n) {   // index == n passes
        return;
    }
    int diff = value - arr[index];  // ArrayIndexOutOfBoundsException

int[] arr = {1, 2, 3, 4, 5};
SegmentTree tree = new SegmentTree(arr.length, arr);

tree.update(5, 100);   // ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
tree.getSum(0, 5);     // returns 15 instead of rejecting the query

getSum(0, 5) is the quieter half of the bug: the out-of-range query reaches getSumTree, matches the qStart <= start && qEnd >= end short circuit at the root and returns the root sum, so the caller gets a plausible-looking number for a range that does not exist.

The constructor is also unguarded. new SegmentTree(0, arr) computes Math.log(0) == -Infinity, which casts to Integer.MIN_VALUE and yields a segment array size of -1, throwing NegativeArraySizeException; a size larger than the array throws ArrayIndexOutOfBoundsException while building the tree.

Fix

• update rejects index >= n and getSum rejects end >= n, preserving the existing contract of returning silently / returning 0 for out-of-range input.
• The constructor validates its arguments up front and throws IllegalArgumentException for a null array or a size outside [1, arr.length].
• Removed a duplicated this.n = n; assignment.

Tests

The class had no test class at all. SegmentTreeTest is added, covering:

• range sums, single-element trees, negative values and updates reflected in later queries

• update at index == n and beyond being ignored instead of throwing — this fails on the old code

• out-of-range queries returning 0, including getSum(0, n) — this fails on the old code

• constructor validation for invalid sizes and a null array

• an exhaustive cross-check of every [start, end] range against a brute-force sum for sizes 1..9, 16 and 17, which covers both the exact powers of two and the sizes in between

• I have read CONTRIBUTING.md.

• This pull request is all my own work -- I have not plagiarized it.

• All filenames are in PascalCase.

• All functions and variable names follow Java naming conventions.

• All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.

• All new algorithms include a corresponding test class that validates their functionality.

• All new code is formatted with clang-format -i --style=file path/to/your/file.java