It shouldn’t be that hard if you know what to store in nodes and how to merge two nodes correctly. If you provide me your code then I’ll figure out why it is giving wrong answer. I’m not very used to implementing segment tree in recursive way. But you can have a look to my solution.
[details=Click to view]
#include
using namespace std;
struct Node{
int MS,SS,PS,S;
// ms- maxsum
// ps- maxprefixsum
// ss- maxsuffixsum
// s- totalsum
Node(){
MS=SS=PS=S=0;
}
};
Node combine(Node& a, Node& b){
Node tmp;
tmp.S = a.S + b.S;
tmp.SS =max(b.SS,b.S+a.SS);
tmp.PS =max(a.PS,a.S+b.PS);
tmp.MS =max(tmp.PS,max(tmp.SS,max(a.MS,max(b.MS,a.SS+b.PS))));
return tmp;
}
Node iniLeaf(int x){
Node tmp;
tmp.S = tmp.SS = tmp.PS = tmp.MS = x;
return tmp;
}
const int N = 1e5;
Node t[2*N];
int n;
void build(){
for(int i=n-1;i>0;i--){
t[i] = combine(t[i<<1], t[i<<1|1]);
}
}
int query(int l, int r){
Node resR,resL;
bool b1,b2;
b1 = false;
b2 = false;
for(l+=n,r+=n;l>=1,r>>=1){
if(l&1){
if(b1==false){
resL = t[l++];
b1 = true;
}else{
resL = combine(resL,t[l++]);
}
}
if(r&1){
if(b2==false){
resR = t[--r];
b2 = true;
}else{
resR = combine(t[--r],resR);
}
}
}
if(b1 && b2){
return combine(resL,resR).MS;
}
if(b1){
return resL.MS;
}
if(b2){
return resR.MS;
}
assert(false);
return 0;
}
int main(){
cin>>n;
int tmp;
for(int i=0;i>tmp;
t[i+n] = iniLeaf(tmp);
}
build();
int q;
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
cout<< query(x-1,y) << endl;
}
return 0;
}