# segment tree problem

problem link :-http://www.spoj.com/problems/GSS1/ why i m getting WA

``````enter code here
#include<iostream>
#include<cmath>
#include<utility>
#include<cstdio>
using namespace std;
int N=50000;
int M[1<<23][2];
int a[1<<23];
void initialize(int node,int i,int j)
{
if(i==j)
{
if(a[i]>0)
M[node][0]=a[i];
else
M[node][0]=0;
M[node][1]=a[i];
}
else
{
initialize(2*node,i,(i+j)/2);
initialize(2*node+1,(i+j)/2+1,j);
M[node][0]=M[2*node][0]+M[2*node+1][0];
M[node][1]=M[2*node][1]>M[2*node+1][1]?M[2*node][1]:M[2*node+1][1];
}
}
pair<int,int> query(int node,int b,int e,int i,int j)
{
pair<int,int>  p1,p2;
if(i>e||j<b)
return make_pair(0,-15008);
if(b>=i&&e<=j)
return make_pair(M[node][0],M[node][1]);
p1=query(2*node,b,(b+e)/2,i,j);
p2=query(2*node+1,(b+e)/2+1,e,i,j);
return make_pair(p1.first+p2.first,max(p1.second,p2.second));

}
int main()
{
pair<int,int> AL;
int m,n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
initialize(1,0,n-1);
cin>>m;
int x,y;
while(m--)
{
cin>>x>>y;
AL=query(1,0,n-1,x-1,y-1);
if(AL.first==0)
cout<<AL.second<<endl;
else
cout<<AL.first<<endl;

}

}``````

It seems to me that you misunderstood the statement (or maybe I did).

You have to find continues sequence in range [x; y], such, that sum of elements in such sequence is max.

So for input

``````3
1 -2 3
1
1 3
``````

you have to return 3, your program returns 4.

@betlista can you please explain how to create 2D Segment Tree and How to update it…

yeah i am too having a hard time understanding that

@betlista i think in the problem statement array in the range need not be contiguous , is it correct ?

No, it is not.
It must be contiguous!
a[i] + a[i+1] + … + a[j] suggests that!!
And problem is to find Maximum Sum of (contiguous) Subarray within index range of x to y.

@selfcompiler >> I think you have misinterpreted the question. You have to find maximum sum of the sub-array in the range A[x…y] for each query. First look at a simple problem of finding maximum sum sub-array in a given array.

//