算法1

C++ 代码

#include<iostream>
#include<cstdio>
#include<climits>

using namespace std;

const int N=100010;
int n,m;
int w[N];

struct Node{
    int l,r;
    int maxv;

}tr[N*4];

void build(int u,int l,int r){//build在一段区间内初始化一段线段树
    if(l==r) tr[u]={l,r,w[r]};//区间内只有一个数，最大值是自己
    else{

        tr[u]={l,r};//先把前两个位置赋值，这是赋值结构体
        int mid=l+r>>1;//然后定义中间值
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);//递归一下左儿子和右儿子
        tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);//求一下左右儿子的最大值


    }
}


int query(int u,int l,int r){

    if(tr[u].l>=l &&tr[u].r<=r) return tr[u].maxv;
    int mid=tr[u].l+tr[u].r>>1;//树里面区间中点
    int maxv=INT_MIN;//INT_MIN是整数最小值，需要加上#include<climits>
    if(l<=mid)maxv=query(u<<1,l,r);//如果左边有交集
    if(r>mid)maxv=max(maxv,query(u<<1|1,l,r));//如果右边有交集

    return maxv;


}
int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    build(1,1,n);
    int l,r;
    while(m--){

        scanf("%d%d",&l,&r);
        printf("%d\n",query(1,l,r));

    }


    return 0;
}