RMQ（Range Minimum/Maximum Query）区间最值查询，即给出长度为n的数组A，以及m组询问s、t(s<=t<=n)，返回区间[s,t]中的最值。
基于线段树的方法实现的话，建树O(n)，查询O(logn)，相比ST，适合用于n更大，m较小的情况。
void built(int k, int l, int r) { if (l==r) t[k] = a[l]; //到叶子上，则赋值 else { built(k*2+1, l, (l+r)/2); //左儿子 built(k*2+2, (l+r)/2, r); //右儿子 t[k] = min(t[k*2+1], t[k*2+2]); //回溯赋值 } } void update(int k, int a) { //叶子节点 k += n-1; t[k] = a; //向上更新 while (k>0) { k = (k-1)/2; t[k] = min(t[k*2+1], t[k*2+2]); } } int query(int a, int b, int k, int l, int r) //查询区间[a,b], 当前查询结点的位置为k, 所表示的区间为[l,r],默认k为根结点 { if (r<=a||b<=l) return INF; //当前区间与所查询区间无交集，返回一个不影响答案的值 if (a<=l&&r<=b) return t[k]; //当前区间包含于所查询区间，直接返回当前区间的最值就好了 else { int vl = query(a, b, k*2+1, l, (l+r)/2); //查询左儿子 int vr = query(a, b, k*2+1, (l+r)/2, r); //查询右儿子 return min(vl, vr); } }