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 combines summaries of disjoint intervals. Minimum is associative, so a parent can combine two child minima. A point replacement repairs only its ancestors; a range query combines fully covered intervals.

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.

// Slot zero is unused; leaves at 4..7 hold [4, 1, 7, 3].
tree := []int{0, 1, 1, 3, 4, 1, 7, 3}
node := 4 + 1 // Public index 1.
tree[node] = 6
for node > 1 {
	node /= 2
	tree[node] = tree[2*node]
	if tree[2*node+1] < tree[node] {
		tree[node] = tree[2*node+1]
	}
}
fmt.Println(tree[1]) // 3: only the changed leaf's ancestors were repaired.

Choosing a range-query structure

Increasing the old minimum exposes why cached prefix minima cannot be subtracted or repaired by one local adjustment. Query identity can be internal infinity, while empty public output is nil. Build in O(n), then update/query in O(log n); no lazy propagation is needed for point replacements.

Build the segment summaries in O(n) time and space, then point replacement and range minimum each take O(log(n+1)) time. Empty ranges need an internal identity and the public API’s absence result. Associativity permits combining covered blocks; an order-sensitive summary must also preserve their left-to-right order.

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