Hello there i'm starting to learn about segment tree and its applications i came across this problem and found very interesting and although i am sure of my solution it keeps getting WA here's the problem
and here is the code
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double eps = 1e-18;
const double PI = atan(1.0);
#define readFile freopen("input","r",stdin);
#define writeFile freopen("output","w",stdout);
#define fastIO ios::sync_with_stdio(0);
typedef unsigned long long ULL;
typedef pair<int,int> ii;
struct Node{
int sum,ls,rs,best;
Node(){}
Node(int sum,int ls,int rs,int best){
this->sum = sum;
this->ls = ls;
this->rs = rs;
this->best = best;
}
};
Node merge(Node n1,Node n2){
int sum,ls,rs,best;
sum = n1.sum+n2.sum;
ls = max(n1.ls,n1.sum+n2.ls);
rs = max(n2.rs,n2.sum+n1.rs);
best = max(n1.best,max(n2.best,n1.rs+n2.ls));
return Node(sum,ls,rs,best);
}
const int N = 50001;
int arr[N];
Node tree[N<<2];
int neg = -1000000000;
Node build(int node,int l,int r){
if (l==r){
return tree[node] = Node(arr[l],arr[l],arr[l],arr[l]);
}
int mid = (l+r) >> 1;
return tree[node] = merge(build(node<<1,l,mid),build(node<<1|1,mid+1,r));
}
Node query(int node,int l,int r,int ll,int rr){
if (l>rr || r<ll) return Node(neg,neg,neg,neg);
if (l>=ll && r<=rr) return tree[node];
int mid = (l+r) >> 1;
return merge(query(node<<1,l,mid,ll,rr),query(node<<1|1,mid+1,r,ll,rr));
}
int main(){
#ifndef ONLINE_JUDGE
readFile; writeFile;
#endif
fastIO;
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
build(1,1,n);
int q; cin>>q;
while (q--){
int a,b; cin>>a>>b;
cout<<query(1,1,n,a,b).best<<"\n";
}
}
Nevermind i found the error it was in the neg value