题目大意就是说给你一个长度为N的区间，并给定区间每个点的值，求Q次询问区间<x，y>之间的最大值与最小值的差
这是我第一道用线段树做的题目^_^
采用线段树记录区间x，y的最大值用最小值，每一次询问的复杂度就是logN总复杂度就是QlogN，详见代码：
1 #include2 #include 3 #include 4 #define MAX(a,b) (a)>(b)?(a):(b) 5 #define MIN(a,b) (a)<(b)?(a):(b) 6 #define MAXN 50010 7 using namespace std; 8 9 struct node10 {11 int x,y;12 int max,min;13 }ma[3*MAXN];14 int H[MAXN],N,Q;15 16 void build_tree(int index,int x,int y)//建树，在回溯时给max与min赋值17 {18 ma[index].x = x;19 ma[index].y = y;20 if(x == y)21 {22 ma[index].max=ma[index].min=H[y];23 return;24 }25 int mid = (x+y)/2;26 build_tree(index*2, x, mid);//构造左子树27 build_tree(index*2+1, mid+1, y);//构造右子树28 ma[index].max = MAX(ma[index*2].max, ma[index*2+1].max);//此区间的最大值就是两颗子树最大值的最大值29 ma[index].min = MIN(ma[index*2].min, ma[index*2+1].min);30 }31 32 int search_max(int index,int x,int y)//找到区间最大值33 {34 if(ma[index].x==x && ma[index].y==y)35 return ma[index].max;36 int mid = (ma[index].x+ma[index].y)/2;37 if(x > mid) //在右子树中38 return search_max(index*2+1, x, y);39 if(y <= mid) //在左树中40 return search_max(index*2, x, y);41 //在两颗子树之间42 int L = search_max(index*2, x, mid);43 int R = search_max(index*2+1, mid+1, y);44 return MAX(L,R);45 }46 47 int search_min(int index,int x,int y)//找到区间最小值48 {49 if(ma[index].x==x && ma[index].y==y)50 return ma[index].min;51 52 int mid = (ma[index].x+ma[index].y)/2;53 if(x > mid)54 return search_min(index*2+1, x, y);55 if(y <= mid)56 return search_min(index*2, x, y);57 int L = search_min(index*2, x, mid);58 int R = search_min(index*2+1, mid+1, y);59 return MIN(L,R);60 61 }62 63 int main()64 {65 while(~scanf("%d%d",&N,&Q))66 {67 int i,x,y;68 for(i = 1; i <= N; i ++ ) scanf("%d", &H[i]);69 build_tree(1, 1, N);70 for(i = 0; i < Q; i ++ )71 {72 scanf("%d%d", &x, &y);73 printf("%d\n", search_max(1,x,y)-search_min(1,x,y));74 }75 }76 return 0;77 }