Spoj GSS1

#include <iostream>
#include<algorithm>
#include <cstdio>
#define ll                                      long long
#define fi                                      freopen("in.txt", "r", stdin)
#define fo                                      freopen("out.txt", "w", stdout)
#define m0(a) memset(a , 0 , sizeof(a))
#define m1(a) memset(a , -1 , sizeof(a))

#define mx 50000+3
using namespace std;

int i, j  ;

class node
{
public:
    int prefix ;
    int suffix ;
    int sum ;
    int result ;

    node(int tem)
    {
        prefix = suffix = sum = result = tem ;
    }

    node()
    {
        prefix = suffix = sum = result = -1000000 ;
    }
};


node combineChild(node a, node b)
{
    node t ;

    t.sum = a.sum + b.sum ;
    t.prefix = max( a.prefix, (a.sum + b.prefix) ) ;
    t.suffix = max( b.suffix, (b.sum + a.suffix) ) ;
    t.result = max( a.suffix + b.prefix, max(a.result, b.result)) ;

    return t ;
}


int A[mx] ;
node seg[mx*4] ;


node buildTree(int lo, int hi, int sp)
{
    if(lo == hi)
    {
        node n ;
        n = node(A[lo]) ;
        seg[sp] = n ;
        return seg[sp] ;
    }

    int mid ;
    mid = (lo+hi) / 2 ;

    node left = buildTree(lo, mid, 2*sp+1) ;
    node right = buildTree(mid + 1, hi, 2*sp + 2) ;

    seg[sp] = combineChild(left, right) ;

    return seg[sp] ;
}


node query(int lo, int hi, int sp)
{
    if(hi < i || lo > j)
    {
        node n;

        return n ;
    }
    if(lo >= i && hi <= j)
    {
        return seg[sp] ;
    }

    int mid ;
    mid = ( lo + hi ) / 2 ;

    node l, r ;

    l = query(lo, mid, 2*sp+1) ;
    r = query(mid + 1, hi, 2*sp + 2 ) ;

    return combineChild(l, r) ;
}

int main()
{
    for(int ii = 0 ; ii < mx ; ii++)
    {
        A[ii] = -1000000 ;
    }

    int N ;
    scanf("%d",&N) ;
    for(int ii = 0 ; ii < N ; ii++)
    {
        scanf("%d",&A[ii]) ;
    }

    buildTree(0, N-1, 1) ;

    int M ;
    scanf("%d",&M) ;

    while(M--)
    {
        scanf("%d %d", &i, &j) ;
        i-- ;
        j-- ;
        int ans ;

        ans = query(0, N-1, 1).result ;
        printf("%d\n",ans);
    }
    return 0 ;
}