here's the updated code:
#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
#define ll long long
int sn,arr[MAX];
struct node{
ll best,sum,lft,ryt;
node(ll a = 0){
best = sum = lft = ryt = a;
}
void merge(node a,node b){
sum = a.sum+b.sum;
lft = max(a.lft, a.sum+b.lft);
ryt = max(b.ryt, a.ryt+b.sum);
best = max(a.ryt+b.lft, max(a.best,b.best));
}
}*segtree=NULL;
node query(int i,int j,int ri,int rj,int curr){
if(rj<i || ri>j)
return node();
if(ri<=i&&rj>=j)
return segtree[curr];
int mid = i + (j-i)/2,l=2*curr+1;
if(j<=mid)
return query(i,j,ri,rj,l);
else if(i>mid)
return query(i,j,ri,rj,l+1);
else{
node a,b,temp;
a = query(i,mid,ri,rj,l);
b = query(mid+1,j,ri,rj,l+1);
temp.merge(a,b);
return temp;
}
}
void build(int i,int j,int curr){
if(i>j)
return;
if(i==j){
segtree[curr] = node(arr[i]);
return;
}
int l = 2*curr+1,mid=i +(j-i)/2,r = 2*curr+2;
build(i,mid,l);
build(mid+1,j,r);
segtree[curr].merge(segtree[l],segtree[r]);
}
void init(int n){
sn = ceil(log2(n)+1);
sn = 2*pow(2,sn);
segtree = (node*)malloc(sn * sizeof(node));
build(0,n-1,0);
}
int main() {
int n,q,ri,rj;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
init(n);
build(0,n-1,0);
scanf("%d",&q);
while(q--){
scanf("%d %d",&ri,&rj);
node temp = query(0,n-1,ri-1,rj-1,0);
printf("%lld\n",temp.best);
}
free(segtree);
return 0;
}