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 composable summary for each interval. Minimum is associative, so disjoint canonical blocks can be combined in any grouping. There is no subtraction operation that removes an old prefix minimum, which is why prefix-sum tricks do not answer range minimum.

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].
std::vector<Int> tree{0, 1, 1, 3, 4, 1, 7, 3};
std::size_t node = 4 + 1; // Public index 1.
tree[node] = 6;
while (node > 1) {
    node /= 2;
    tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
}
std::cout << tree[1] << '\n'; // 3: the right-half summary stayed unchanged.

Choosing a range-query structure

An optional identity distinguishes an empty range from a real value equal to a numeric sentinel. Build leaves from the initial input and combine parents bottom-up in O(n). A set operation replaces one leaf and recomputes its ancestors; a half-open query visits O(log n) blocks. Be precise about replacement: adding the supplied value would solve a different update API. Keep internal storage independent of the original vector, including when a later command is invalid. A scan prototype is a practical oracle for update/query interleavings.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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