线段树

这个模板用于求区间最值(也适用于修改点的)，我还有个线段树区间修改那个,还可以求和,当然这个也可以,只是还没加上去.

#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不适用.
    }
}