Spoj Problem GSS1 - Can you answer these Queries I using Segment Trees

Problem Statement:-http://www.spoj.com/problems/GSS1/

Hint:-Use Segment Tree.

Using the Segment trees,this problem can be solved within the given time limit.we have to maintain four values for prefix,suffix,prefix + suffix, and  maximum of these three

C Program:-

#include<stdio.h>

struct Node{

int sum;

int prefix;

int suffix;

int max;

void init(int value){

sum=value;

prefix=value;

suffix=value;

max=value;

}

void merge(Node l,Node r){

if(l.sum==-99999&&l.prefix==-99999&&l.suffix==-99999&&l.max==-99999){

sum=r.sum;

prefix=r.prefix;

suffix=r.suffix;

max=r.max;

return;

}

if(r.sum==-99999&&r.prefix==-99999&&r.suffix==-99999&&r.max==-99999){

sum=l.sum;

prefix=l.prefix;

suffix=l.suffix;

max=l.max;

return;

}

sum=l.sum+r.sum;

prefix=maxInt(l.prefix,l.sum+r.prefix);

suffix=maxInt(r.suffix,r.sum+l.suffix);

max=maxInt(l.suffix+r.prefix,maxInt(l.max,r.max));

}

int maxInt(int x,int y){

        return x>y?x:y;

        }

};

int getSize(int N){

int s=1;

while(s<N){

s<<=1;

}

s<<=1;

return s-1;

}

void createSegArray(Node segAr[],int ar[],int low,int high,int pos){

if(low==high){

segAr[pos].init(ar[low]);

return;

}

int mid=(low+high)/2;

createSegArray(segAr,ar,low,mid,2*pos+1);

createSegArray(segAr,ar,mid+1,high,2*pos+2);

segAr[pos].merge(segAr[2*pos+1],segAr[2*pos+2]);

}

Node temp={-99999,-99999,-99999,-99999};

Node result={0,0,0,0};

Node executeQuery(Node segAr[],int qL,int qR,int low,int high,int pos){

if(qL<=low&&qR>=high){

return segAr[pos];

}

if(qL>high||qR<low){

return temp;

}

int mid=(low+high)/2;

Node l,r;

l=executeQuery(segAr,qL,qR,low,mid,2*pos+1);

r=executeQuery(segAr,qL,qR,mid+1,high,2*pos+2);

result.merge(l,r);

return result;

}

int main(){

int N;

scanf("%d",&N);

int ar[N];

for(int i=0;i<N;i++){

scanf("%d",&ar[i]);

}

Node segAr[getSize(N)];

createSegArray(segAr,ar,0,N-1,0);

int nQ,L,R;

scanf("%d",&nQ);

while(nQ--!=0){

scanf("%d %d",&L,&R);

printf("%d\n",executeQuery(segAr,L-1,R-1,0,N-1,0).max);

}

return 0;

}

Input:-

3
-1 2 3
1
1 2

Output:-

2

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------