maximum contiguous sum in the range [l,r] .

                                                 http://www.spoj.com/problems/GSS1/

GSS1 - Can you answer these queries I

In this question we have to find the maximum contiguous sum in the range[l,r]. 

To find this 

1) total sum is required 

2) suffix max is required 

3) prefix max is required = max(left child prefix max ,  left child sum + ri8 child prefix max ).

4) maximum contiguous = max ( ri8 child maximum contiguous , left child maximum contiguous,

                                                          left child suffix max + ri8 child prefix max )           

                                           







#include<bits/stdc++.h>

using namespace std;


struct node
{
  long  presum;
  long  sufsum;
  long  tmax;
  long  tsum;
};

typedef struct node grp;

grp tre[50005*4];

long a[50005];

int n;


long maxi(long x, long y) {
    return x > y ? x : y;
}


void build(int node,int st,int en)
{
  if(st==en)
  {
     tre[node].presum=a[st];
     tre[node].sufsum=a[st];
     tre[node].tmax=a[st];
     tre[node].tsum=a[st];
  }
  else
  {
     build(2*node,st,(st+en)/2);
     build(1+2*node,1+(st+en)/2,en);

     tre[node].tsum=tre[2*node].tsum+tre[2*node+1].tsum;

     long ok=maxi(tre[2*node].tmax,tre[2*node+1].tmax );
     ok=maxi(ok, tre[2*node].sufsum+tre[2*node+1].presum);
     tre[node].tmax=ok;


     tre[node].presum=maxi(tre[2*node].presum   ,  tre[2*node].tsum  + tre[2*node+1].presum);

     tre[node].sufsum=maxi(tre[2*node+1].sufsum ,  tre[2*node+1].tsum + tre[2*node].sufsum);
  }
}



grp query(int node, int st, int en, int fs, int fe)
{
   if(st>=fs && en<=fe)
   {
       return tre[node];
   }

   int md=(st+en)/2;
   if(fe<=md)
     return query(2*node,st,(st+en)/2,fs,fe);

   if(fs>md)
     return query(1+2*node,1+(st+en)/2,en,fs,fe);


     grp temp1=query(2*node,st,(st+en)/2,fs,fe);
     grp temp2=query(1+2*node,1+(st+en)/2,en,fs,fe);

      grp sent;

      sent.tsum=temp1.tsum+temp2.tsum;

      long ok=maxi(temp1.tmax, temp2.tmax);
      ok=maxi(ok,temp1.sufsum+temp2.presum);
      sent.tmax=ok;

      sent.presum=maxi(temp1.presum   ,  temp1.tsum  + temp2.presum);

      sent.sufsum=maxi(temp2.sufsum ,    temp2.tsum +  temp1.sufsum);

     return sent;
}




int main()
{
   int i,q,l,r;
   scanf("%d",&n);


  for(i=0;i<n;i++)
  scanf("%ld",&a[i]);

  build(1,0,n-1);

 scanf("%d",&q);
 for(i=0;i<q;i++)
 {
     scanf("%d%d",&l,&r);

     grp ans=query(1,0,n-1,l-1,r-1);

     printf("%ld\n",ans.tmax);
 }
return 0;
}