Dynamic range minimum queries

easy ~15 min

You get an array of n integers and a list of queries, processed in order. Positions are 1-indexed.

(1, k, u): set the value at position k to u.
(2, a, b): report the minimum of positions a..b inclusive.

Write range_min_queries(nums, queries) -> list[int] returning the answers to the type-2 queries, in order.

range_min_queries([6, 2, 9, 4], [(2, 1, 4), (1, 2, 8), (2, 1, 4), (2, 3, 3)])
# [2, 4, 9]

Constraints: 1 <= n <= 2·10^5, up to 2·10^5 queries; values in 1..10**9. Taking min of the slice per query is O(n); aim for O(log n) per query.

Show hint

Precompute the minimum of a hierarchy of blocks (pairs, groups of four, and so on). Any range is then covered by O(log n) blocks, and an assignment only changes the O(log n) blocks that contain that position.

Topic: Segment tree (+ lazy propagation). Any associative range query with point or range updates in O(log n).

Read the visual guide