本文共 1957 字，大约阅读时间需要 6 分钟。
N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。
第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行，每行两个整数L,R(1≤L≤R≤N)。
对于每个询问输出一行，一个整数表示区间内的极差。
| Sample Input | Sample Output |
|---|---|
5 33 2 7 9 101 52 33 5 | 853 |
题目链接：http://acm.uestc.edu.cn/#/contest/show/155
分析：线段树点更新裸题，继续复习线段树，这题要算的是极差，只需要建树和查询两部分，无需更新，所以建树的时候只要去求最大值和最小值即可，然后极差一减得出答案！
下面给出AC代码：
1 #include2 using namespace std; 3 const int N=200020; 4 struct Node 5 { 6 int l,r,minn,maxn; 7 }tree[N<<2]; 8 void build(int l,int r,int pos) 9 {10 tree[pos].l=l;11 tree[pos].r=r;12 if(l==r)13 {14 scanf("%d",&tree[pos].maxn);15 tree[pos].minn=tree[pos].maxn;16 return;17 }18 int mid=(l+r)/2;19 build(l,mid,pos*2);20 build(mid+1,r,pos*2+1);21 tree[pos].maxn=max(tree[pos*2].maxn,tree[pos*2+1].maxn);22 tree[pos].minn=min(tree[pos*2].minn,tree[pos*2+1].minn);23 }24 int query1(int l,int r,int pos)25 {26 if(tree[pos].l==l&&tree[pos].r==r)27 return tree[pos].minn;28 int mid=(tree[pos].l+tree[pos].r)/2;29 if(r<=mid)30 return query1(l,r,pos*2);31 else if(l>mid)32 return query1(l,r,pos*2+1);33 else return min(query1(l,mid,pos*2),query1(mid+1,r,pos*2+1));34 }35 int query2(int l,int r,int pos)36 {37 if(tree[pos].l==l&&tree[pos].r==r)38 return tree[pos].maxn;39 int mid=(tree[pos].l+tree[pos].r)/2;40 if(r<=mid)41 return query2(l,r,pos*2);42 else if(l>mid)43 return query2(l,r,pos*2+1);44 else return max(query2(l,mid,pos*2),query2(mid+1,r,pos*2+1));45 }46 int main()47 {48 int x,y;49 scanf("%d%d",&x,&y);50 build(1,x,1);51 while(y--)52 {53 int p,q;54 scanf("%d%d",&p,&q);55 printf("%d\n",query2(p,q,1)-query1(p,q,1));56 }57 return 0;58 }
转载地址：http://nakia.baihongyu.com/