Introduction to Segment Tree Pattern

You are given an array and two kinds of request, mixed together in any order. Report the smallest value in a range, and change the value at one position.

[5, 2, 7, 1]
smallest in range 1 to 2?   min(2, 7) = 2
set position 1 to 9
smallest in range 1 to 2?   min(9, 7) = 7

Prefix Sum answered range questions in one subtraction. It cannot answer this one, for two reasons. Minimum does not subtract, and any change to the array invalidates every prefix entry after it.

Two plain approaches each fail on one side. Scanning the range costs O(N) per query. Precomputing every range costs