线段树模板体，线段树建树和查询用到了分治思想，递归写起来还算顺手。
#include <algorithm> #include <bitset> #include <cassert> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> using namespace std; typedef long long ll; #define maxn 50010 #define inf 0x3fffffff int nmin , nmax; struct node { int l,r; int nmin , nmax; }tree[3*maxn]; int num[maxn]; void build (int i,int l,int r){ tree[i].l = l; tree[i].r = r; if (l==r){ tree[i].nmin = num[l]; tree[i].nmax = tree[i].nmin; return; } else { int mid = (l+r)/2; build (2*i,l,mid); build (2*i+1,mid+1,r); tree[i].nmin = min (tree[i*2].nmin,tree[i*2+1].nmin); tree[i].nmax = max (tree[i*2].nmax,tree[i*2+1].nmax); } } void query (int i,int l,int r){ if (tree[i].l ==l && tree[i].r==r ){ nmin = min (nmin ,tree[i].nmin); nmax = max (nmax ,tree[i].nmax); return ; } int mid = (tree[i].l +tree[i].r)>>1; if (r <= mid)query ( 2*i,l,r); else if (l>mid) query ( 2*i+1,l,r); else { query ( i*2 , l, mid); query (2*i+1 , mid+1 ,r); } } int main() { int n,q; int l,r; while (scanf ("%d %d",&n,&q)!=EOF){ for (int i=1;i<=n;i++){ scanf ("%d",&num[i]); } build (1,1,n); for (int i =1;i<=q;i++){ scanf ("%d %d",&l,&r); nmax = -inf; nmin = inf; query (1,l,r); printf("%d\n", nmax - nmin); } } return 0; }