• 题面
    给定给定含n个数的数组A[N],求区间[L,R]的和
    数组个数为n,q次查询区间l,r;

  • 数据范围
    1<=n<=105,1<=L,R<=n,0<a[i]<1031<=n<=10^5,1<=L,R<=n,0<a[i]<10^3
    1<=Q<=1051<=Q<=10^5

#define ll long long
#define lc num<<1
#define rc num<<1|1
#define N 100001
#include<bits/stdc++.h>
using namespace std;
int n,l,r,q;
ll a[N];
struct node{
    int l,r,num;
    ll val,add;
}tre[N*4];
void pushup(int num)
{
    tre[num].val=max(tre[lc].val,tre[rc].val);
}
void build_tre(int l,int r,int num)
{
    tre[num].l=l;tre[num].r=r;
    if(l==r)
    {
        tre[num].val=a[l];
        return ;
    }
    int mid=(tre[num].l+tre[num].r)>>1;
    build_tre(l,mid,lc);
    build_tre(mid+1,r,rc);
    pushup(num);
}
ll query_itv(int l,int r,int num)
{
    ll ans=-0x3f;
    if(tre[num].l>=l&&tre[num].r<=r)
    {
        return tre[num].val;
    }
    int mid=(tre[num].l+tre[num].r)>>1;
    if(l<=mid) ans=max(ans,query_itv(l,r,lc));
    if(r>mid) ans=max(ans,query_itv(l,r,rc));
    return ans;
}

signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build_tre(1,n,1);
    // cout<<tre[1].val;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d %d",&l,&r);
        printf("%lld\n",query_itv(l,r,1));
    }
    return 0;
}