[板子]用线段树解决ST表问题

ST表可以参考：http://blog.csdn.net/whistlena/article/details/52191463

简单说就是区间RMQ最值问题。

对解决这种问题，线段树不用用啥啊。

扔一个Code：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node{
 7     int val;
 8 }segTree[400005];
 9 int a[100005];
10 void build(int root,int arr[],int istart,int iend){
11     if(istart==iend){
12         segTree[root].val=arr[istart];
13     }else{
14         int mid=(istart+iend)/2;
15         build(root*2,arr,istart,mid);
16         build(root*2+1,arr,mid+1,iend);
17         segTree[root].val=max(segTree[root*2].val,segTree[root*2+1].val);
18     }
19 }
20 int query(int root,int nstart,int nend,int qstart,int qend){
21     if(qstart>nend||qend<nstart){
22         return 0;
23     }if(qstart<=nstart&&qend>=nend){
24         return segTree[root].val;
25     }
26     int mid=(nend+nstart)/2;
27     return max(query(root*2,nstart,mid,qstart,qend),query(root*2+1,mid+1,nend,qstart,qend));
28 }
29 int main(){
30     int n,m;
31     scanf("%d%d",&n,&m);
32     for(int i=1;i<=n;i++){
33         scanf("%d",&a[i]);
34     }
35     build(1,a,1,n);
36     int x,y;
37     for(int i=1;i<=m;i++){
38         scanf("%d%d",&x,&y);
39         printf("%d
",query(1,1,n,x,y));
40     }
41     return 0;
42 }

你可以凭借这个Aluogu的T3865