题目地址
最基础的线段树题目，很明显的区间操作，所以第一时间要想到线段树
用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的），
以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更新效率最坏就可能变成O(n)的了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+5;
const int INF=(1<<30);
int minV,maxV;
struct CNode{int L,R;int minV,maxV;int Mid(){return (L+R)/2;}
}tree[maxn*3]; //3*n就够了
void BuildTree(int root,int L,int R)
{tree[root].L=L;tree[root].R=R;tree[root].maxV=-INF;tree[root].minV=INF;if(L!=R){int mid=tree[root].Mid();BuildTree(root*2+1,L,mid);BuildTree(root*2+2,mid+1,R);}
}
void insert(int root,int i,int v)
{if(tree[root].L==tree[root].R){tree[root].maxV=tree[root].minV=v;return;}tree[root].minV=min(tree[root].minV,v);tree[root].maxV=max(tree[root].maxV,v);int mid=tree[root].Mid(); if(i<=mid) insert(root*2+1,i,v);else insert(root*2+2,i,v);
}
void Query(int root,int s,int e)
{if(tree[root].minV>=minV&&tree[root].maxV<=maxV) return;if(tree[root].L==s&&tree[root].R==e){minV=min(minV,tree[root].minV);maxV=max(maxV,tree[root].maxV);return;}int mid=tree[root].Mid();if(e<=mid) Query(2*root+1,s,e);else if(s>mid) Query(2*root+2,s,e);else {Query(2*root+1,s,mid);Query(2*root+2,mid+1,e);}
}
int main()
{int N,Q,x;scanf("%d%d",&N,&Q);BuildTree(0,1,N);for(int i=1;i<=N;i++){scanf("%d",&x);insert(0,i,x);}for(int i=0;i<Q;i++){int s,e;scanf("%d%d",&s,&e);minV=INF,maxV=-INF;Query(0,s,e);cout<<maxV-minV<<endl;}return 0;
}