http://blog.csdn.net/luckcircle/article/details/53088099
博客有详解，不会的童鞋可以去看一下
#include<stdio.h>
struct node{
	int max;
	int min;
	int left;
	int right;
}Node[50005*3];
int min (int a,int b)
{
    return a > b?b:a;
}
int max (int a,int b)
{
    return a > b?a:b;
}
int a[50005];
int low=1000001,hei=0;
void buildtree(int father,int left,int right){
	Node[father].left=left;
	Node[father].right=right;
	
	if(left==right){
		Node[father].max=a[left];
		Node[father].min=a[right];
		return;
	}
	else{
		buildtree(father*2,left,(left+right)/2);
		buildtree(father*2+1,(left+right)/2+1,right);
		if(Node[father*2].max>=Node[father*2+1].max){
			Node[father].max=Node[father*2].max;
		}
		else{
			Node[father].max=Node[father*2+1].max;
		}
		if(Node[father*2].min<Node[father*2+1].min){
			Node[father].min=Node[father*2].min;
		}
		else{
			Node[father].min=Node[father*2+1].min;
		}
	}
}
 void query(int father, int left, int right)    
    {    
        int mid;    
        if(Node[father].left==left&&Node[father].right==right){
        	low=min(low,Node[father].min);
        	hei=max(hei,Node[father].max);
        	return;
		}
		mid=(Node[father].left+Node[father].right)/2;
        if(right<=mid){
        	query(father*2,left,right);
		}
		else if(left>=mid+1){
			query(father*2+1,left,right);
		}
		 else
  		{
        query(father*2,left,mid);
        query(father*2+1,mid+1,right);
    }
}
int main(){
	int i,n,q,left,right;
	scanf("%d %d",&n,&q);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	buildtree(1,1,n);
	for(i=1;i<=q;i++){
		scanf("%d %d",&left,&right);
		query(1,left,right);
		printf("%d\n",hei-low);
		low = 1000001;
		hei = 0;
	}
}