Segment trees

A facilities dashboard shows the minimum temperature over a selected interval. New calibration results sometimes replace an old reading, so the data changes between queries. Scanning every selected range is easy, but long ranges and frequent corrections make that expensive.

Prefix minima don't solve the problem: if the smallest old reading increases, a cached minimum doesn't tell you its replacement. A segment tree keeps enough interval summaries to repair the affected path and reuse unaffected ranges.

Correcting a reading without rescanning every range

Process point replacements and half-open range minima, returning absence for empty ranges. Increasing the old minimum must change every affected ancestor summary.

Copy-and-scan repeats range work. A segment tree combines child summaries, but an update that only compares the old parent with the replacement cannot remove a stale smaller value.

Repairing the summaries that depend on it

For [4, 1, 7, 3], the two half-minima are one and three. Replacing index one with six changes the left minimum to four and the overall minimum to three; the right summary stays valid. A query for [1, 4) combines the updated leaf with the stored right-half minimum. Only summaries whose intervals include the corrected reading need repair.

A segment tree combines interval minima. Point replacement requires recomputing ancestors from both children; merely taking min(old,new) leaves stale minima after an increase. Null is the identity for an empty query and must be handled explicitly. Final O(n) construction/space and O(log n) updates/queries.

An ancestor must be rebuilt from its current children after replacement, rather than retaining its old minimum:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long oldParent = 1;
        long newLeft = 9, unchangedRight = 5;
        long stale = Math.min(oldParent, newLeft);
        long repaired = Math.min(newLeft, unchangedRight);
        assert stale == 1;
        assert repaired == 5;
    }
}

The stale value no longer exists in either child. A complete implementation needs interval-aware queries and an explicit empty identity; using a numeric default for empty ranges would conflate absence with a valid minimum.

Choosing a range-query structure

Segment trees support mutable interval summaries when the combine operation is associative. Choose the stored summary and empty identity carefully; extending to range updates requires additional lazy-propagation invariants.

Update("set", index, value) replaces an internal value; Update("min", left, right) queries [left,right). Return only query minima in order and null for empty ranges. Reject unknown operations, invalid set indices, and ranges unless 0 <= left <= right <= n. Negative values are valid.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

Whole-interval corrections would need another update design; this tree repairs one replaced reading at a time.