Coldest Reading in a Range

A weather station stores one temperature per minute. Readings are sometimes corrected, and forecasters keep asking for the coldest reading between two minutes, and when it happened. Build a RangeMin class:

• RangeMin(temps) starts from the list of whole-number readings temps.
• update(i, value) changes the reading at index i to value.
• coldest(left, right) looks at the readings in the slice [left:right] (left included, right not) and returns a tuple (value, index): the lowest reading and its index. If the lowest value appears more than once in that range, return the smallest of those indexes.

Each call should take about log n steps, where n = len(temps).

Examples

rm = RangeMin([4, -2, 7, -2, 5])
rm.coldest(0, 5)     # returns (-2, 1)    (indexes 1 and 3 both hold -2)
rm.coldest(2, 5)     # returns (-2, 3)
rm.update(1, 9)
rm.coldest(0, 3)     # returns (4, 0)
rm.coldest(4, 5)     # returns (5, 4)

Constraints

• 1 <= len(temps) <= 100,000; readings are whole numbers between -10^9 and 10^9
• 0 <= i < len(temps) and 0 <= left < right <= len(temps), so a range is never empty
• Up to 40,000 calls. Scanning the range on every call is too slow when ranges are tens of thousands of readings long.