I implemented segment tree. Yet I’m getting TLE in 9th test case. Pls help
My code is given below:
#include <iostream>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
struct node{
ll sum=0;
ll pre=0;
ll suf=0;
ll max=0;
};
struct segtree{
ll n;
node *tree;
segtree(ll n, ll *array){
this->n=n;
tree=new node[4*50000];
build_tree(array);
}
node merge(node n1,node n2){
node x;
x.sum=n1.sum+n2.sum;
x.pre=(n1.pre>n1.sum+n2.pre)?n1.pre:n1.sum+n2.pre;
x.suf=(n2.suf>n2.sum+n1.suf)?n2.suf:n2.sum+n1.suf;
x.max=(n1.max>n2.max)?n1.max:n2.max;
x.max=(n1.suf+n2.pre>x.max)?n1.suf+n2.pre:x.max;
return x;
}
void build_tree(ll *array,ll curr=0,ll rs=0,ll re=-1){
if(re==-1)
re=n-1;
if(rs==re){
tree[curr].sum=array[rs];
tree[curr].pre=array[rs];
tree[curr].suf=array[rs];
tree[curr].max=array[rs];
return;
}
ll mid=(rs+re)>>1;
build_tree(array,(curr<<1)+1,rs,mid);
build_tree(array,(curr<<1)+2,mid+1,re);
tree[curr]=merge(tree[(curr<<1)+1],tree[(curr<<1)+2]);
return;
}
node query(ll l,ll r,ll curr=0,ll rs=0,ll re=-1){
if(re==-1)
re=n-1;
if(rs==re){
return tree[curr];
}
ll mid=(rs+re)>>1;
if(r<=mid){
return query(l,r,(curr<<1)+1,rs,mid);
}
if(l>mid){
return query(l,r,(curr<<1)+2,mid+1,re);
}
node n1=query(l,mid,(curr<<1)+1,rs,mid);
node n2=query(mid+1,r,(curr<<1)+2,mid+1,re);
node n3=merge(n1,n2);
return n3;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
ll array[n];
for(ll i=0;i<n;i++){
cin>>array[i];
}
segtree sg(n,array);
ll m;
cin>>m;
while(m--){
ll x,y;
cin>>x>>y;
cout<<sg.query(x,y).max<<endl;
}
return 0;
}