这个模板用于求区间最值(也适用于修改点的)，我还有个线段树区间修改那个,还可以求和,当然这个也可以,只是还没加上去.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf=99999999;
int n,m,q;
int node[200005][2];
void init(int n)
{
int i;
m=1;
while(m<n)
{
m=m<<1;
}
for(i=0; i<2*m-1; i++)
{
node[i][0]=inf;
node[i][1]=-1;
}
}
void update(int x,int v)
{
x+=m-1;
node[x][0]=v;
node[x][1]=v;
while(x>0)
{
x = (x-1)/2.0;
node[x][0]=min(node[x*2+1][0],node[x*2+2][0]);
node[x][1]=max(node[x*2+1][1],node[x*2+2][1]);
}
}
int querymin(int a,int b,int l,int r,int k)
{
int vl,vr;
if(r<=a||l>=b)
{
return inf;
}
if(l>=a&&r<=b)
{
return node[k][0];
}
else
{
vl=querymin(a,b,l,(l+r)/2,k*2+1);
vr=querymin(a,b,(l+r)/2,r,k*2+2);
return min(vl,vr);
}
}
int querymax(int a,int b,int l,int r,int k)
{
int vl,vr;
if(r<=a||l>=b)
{
return -1;
}
if(l>=a&&r<=b)
{
return node[k][1];
}
else
{
vl=querymax(a,b,l,(l+r)/2,k*2+1);
vr=querymax(a,b,(l+r)/2,r,k*2+2);
return max(vl,vr);
}
}
int main()
{
int i,temp,l,r;
int minn,maxx;
scanf("%d%d",&n,&q);
init(n);
for(i=0; i<n; i++)
{
scanf("%d",&temp);
update(i,temp);
}
for(i=0; i<q; i++)
{
scanf("%d%d",&l,&r);
minn=querymin(l-1,r,0,m,0);//询问最小值
maxx=querymax(l-1,r,0,m,0);//询问最大值.
printf("%d\n",maxx-minn);//还是求最大值与最小值的差,只是这个支持修改某一个值,而rmq不适用.
}
}
