The smallest, with changes

Write a segment tree (lesson 4) for the smallest value in a range, while values change. MinTree(a) builds it from a list; set(i, v) changes position i to v; smallest(l, r) returns the smallest value of a[l:r].

m = MinTree([5, 2, 7, 4, 6, 1, 8, 3])
m.smallest(0, 8)    # 1
m.smallest(2, 5)    # 4
m.set(5, 9)
m.smallest(2, 8)    # 3

Every range is half-open, as in Python slices: (l, r) means positions l up to but not including r, the same values as a[l:r].

The list can have any length, not only a power of two. Ranges are never empty.

One test passes in numbers that count how often they are compared with <, <=, > or >= (min and max compare too). They behave like ordinary numbers otherwise. This is how the tests tell the method apart from slower ones, which a timer cannot always do.

Limits

• Up to 100,000 values and 60,000 operations. Each set and smallest should use O(log n) comparisons.