输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y这段区间内的最大数。 输入格式 第一行两个整数 N,M表示数字的个数和要询问的次数； 接下来一行为 N个数；接下来 M行，每行都有两个整数 X,Y。 输出格式 输出共 M行，每行输出一个数。 数据范围 1≤N≤105,1≤M≤106,1≤X≤Y≤N, 数列中的数字均不超过231−1 输入样例： 10 2 3 2 4 5 6 8 1 2 9 7 1 4 3 8 输出样例： 5 8
线段树叶子节点是元素值，一个父节点不超过两个子节点，用线段树维护前缀和是通过计算子节点值的和得到父节点的值，而且求多个数的最大值从比较两个数开始，所以线段树也可以用来维护区间的最大值，修改相应逻辑即可。
AC代码：
#include<stdio.h> #include<algorithm> const int N=100010; int data[N],tr[4*N]; void build(int node,int l,int r) { if(l==r) tr[node]=data[l]; else { int mid=l+((r-l)>>1); int left_node=node<<1; int right_node=(node<<1)|1; build(left_node,l,mid); build(right_node,mid+1,r); tr[node]=std::max(tr[left_node],tr[right_node]); } } int query(int node,int l,int r,int a,int b) { if(a>r||b<l) return -0x7f7f7f7f; else if(a<=l&&b>=r||l==r) return tr[node]; else { int mid=l+((r-l)>>1); int left_node=node<<1; int right_node=(node<<1)|1; int left_max=query(left_node,l,mid,a,b); int right_max=query(right_node,mid+1,r,a,b); return std::max(left_max,right_max); } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&data[i]); build(1,1,n); int x,y; for(int i=0;i<m;++i) { scanf("%d%d",&x,&y); printf("%d\n",query(1,1,n,x,y)); } return 0; }