题目链接：
题意：传统的RMQ是一个不变的数组a求区间最值。现在要循环移动（往前移动）。
分析：求区间问题，很容易想到线段树，移动就相当于单点更新。
建树，有两种方案，第一种是nlogn，就是不断的更新，更新logn，有n个数。
1 #include2 3 using namespace std; 4 5 6 const int INF = 1000000000; 7 const int maxnode = 1<<18; 8 9 int op, qL, qR, p, v; //qL,qR询问区间,p修改点,v修改值10 11 struct IntervalTree12 {13 int minv[maxnode];14 15 //修改：A[p] = v;16 void update (int o,int L,int R)17 {18 int M = L + (R-L)/2;19 if(L==R) minv[o] = v;20 else21 {22 if(p<=M) update(o*2,L,M);23 else update(o*2+1,M+1,R);24 minv[o] = min(minv[o*2],minv[o*2+1]);25 }26 }27 28 //询问[ql,qr]中的最小值29 int query(int o,int L,int R)30 {31 int M = L+(R-L)/2,ans = INF;32 if(qL<=L&&R<=qR) return minv[o];33 if(qL<=M) ans = min(ans,query(o*2,L,M));34 if(M
第二种是有一个build的过程，先将数组存起来，然后build，应用到要维护的信息上去。
1 #include2 3 using namespace std; 4 5 6 const int INF = 1000000000; 7 const int maxnode = 1<<18; 8 9 const int maxn = 100000 + 10; 10 int A[maxn]; 11 int op, qL, qR, p, v; 12 13 struct IntervalTree 14 { 15 int minv[maxnode]; 16 17 18 void build(int o,int L,int R) 19 { 20 int M = L + (R-L)/2; 21 if(L==R) minv[o] = A[L]; 22 else 23 { 24 build(o*2,L,M); 25 build(o*2+1,M+1,R); 26 minv[o] = min(minv[o*2],minv[o*2+1]); 27 } 28 } 29 30 //点修改 d[p] =v; 31 void update(int o,int L,int R) 32 { 33 int M = L + (R-L)/2; 34 if(L==R) minv[o] = v; 35 else 36 { 37 if(p<=M) update(o*2,L,M); 38 else update(o*2+1,M+1,R); 39 minv[o] = min(minv[o*2],minv[o*2+1]); 40 } 41 } 42 43 int query(int o,int L,int R) 44 { 45 46 int M = L + (R-L)/2,ans=INF; 47 if(qL<=L&&R<=qR) 48 return minv[o]; 49 50 if(qL<=M) ans = min(ans,query(o*2,L,M)); 51 if(M