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

A segment tree stores a summary for each interval, with a parent combining its two children's summaries. Minimum is associative: regrouping the same intervals does not change the result. This supports point replacement and range minimum without rescanning every covered value.

A copied-array prototype replaces values directly and scans queries. Prefix minima cannot answer arbitrary ranges by subtraction: minimum has no inverse that removes an earlier prefix's contribution.

Repairing the summaries that depend on it

For [4, 1, 7, 3], the left half has minimum 1, the right half 3, and the root 1. Replacing index 1 with 6 changes the left half to 4 and the root to 3. Only ancestors of that leaf depend on the changed value; other stored summaries remain valid.

A query decomposes its half-open interval into fully covered tree blocks. At each level only the boundary blocks require further splitting, so a balanced tree visits logarithmically many summaries. Build leaves once and combine parents bottom-up for linear construction; rebuilding after each set defeats the intended update bound.

Infinity can act as an internal empty minimum identity because Math.min(Infinity,x) is x. The public empty-range result is null, however; never leak Infinity or use falsiness to confuse a real zero with absence. If implementing index arithmetic with JavaScript bitwise operators, account for their signed 32-bit coercion; arithmetic parent calculations avoid silently narrowing safe Number indices.

const emptyIdentity = Infinity;
console.log(Math.min(emptyIdentity, -4)); // -4
const halves = [4, 3]; // after changing [4,1] into [4,6]
console.log(Math.min(...halves)); // 3: recomputed root from child summaries

Choosing a range-query structure

Final construction and storage are O(n), with O(log(n+1)) point replacements and queries, excluding returned answers. Associativity is required; commutativity is not required for every segment-tree aggregate, so preserve block order for order-sensitive summaries. Lazy range updates are a separate extension. For a few short queries, a scan remains simpler; for point additions and sum queries, Fenwick is compact.

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