2004. The Smallest in a Range, While Values Change
An array of n integers is given, numbered from 1. Then q operations arrive:
set i v replace position i with v
min l r print the smallest value in positions l through r inclusive
Print one line for each min.
3 1 4 1 5
min 1 5 -> 1
set 2 9 the array becomes 3 9 4 1 5
min 1 3 -> 3
min 2 2 -> 9
## What most people try first
The Fenwick tree from problem 2001, with minimum in place of addition. It is a reasonable guess and it does not work, and the reason is worth understanding because it decides which structure a problem needs.
A Fenwick tree answers a PREFIX and gets a range by subtracting one prefix from
another. Subtraction works for sums because addition has an inverse. Minimum has
none: knowing min(1..r) and min(1..l-1) tells you nothing about
min(l..r). A Fenwick tree can do prefix minimum, but not range minimum with
updates that raise a value.
Scanning the range instead is O(n) per query, so 2 * 10^5 queries over
2 * 10^5 values is 4 * 10^10 comparisons.
## A tree over the array
A segment tree stores an answer for every node, where a leaf holds one element and an internal node holds the answer for the union of its children:
t[node] = min(t[left child], t[right child])
Build it once bottom up. To update a position, rewrite its leaf and recompute
its ancestors, which is one node per level. To query l .. r, walk in from both
ends combining the nodes that lie entirely inside the range.
set(i, v): t[n+i] = v; i = (n+i)/2; while i: t[i] = min(t[2i], t[2i+1]); i /= 2
min(l, r): combine every maximal node fully inside [l, r)
## What the merge has to satisfy
The only requirement is that combining is ASSOCIATIVE, so that grouping the range into nodes any way gives the same answer. Minimum, maximum, sum, gcd and bitwise and are all associative, so the identical tree answers all of them by changing one line. No inverse is needed, which is exactly what a Fenwick tree demanded and what this structure does without.
## The boundary
A query where l equals r asks about a single element and must return that
element, not the identity value. And the identity for minimum has to be larger
than any real value: seeding it with 0 reports 0 for any range of positive
numbers, which is the classic wrong answer here. Values reach 10^9, so the
identity must exceed that.
## Cost
O(n) to build, O(log n) per operation, about 18 steps at n = 200000, so
3.6 * 10^6 node visits for 2 * 10^5 operations. Memory is 2n nodes.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `1 ≤ i ≤ n` and `-10^9 ≤ v ≤ 10^9` - `1 ≤ l ≤ r ≤ n`
Input
The first line contains two integers n and q.
The second line contains n integers, the starting values.
Each of the next q lines is either set i v or min l r.
Output
Print one integer on its own line for every min operation, in the order the operations arrive. A set prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.