GSS3 - Can you answer these queries III

/**

@author - Rumman BUET CSE'15
Rumman_Rulez

problem - GSS3 SPOJ
Date - 22 / 4 / 17

Concept -
    Segment Tree

    * If you haven't solved GSS1 yet , go and solve it first.
    * GSS1 + Update = GSS3


*/


#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 50003
using namespace std;

int i, j, idx ;

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)) ;

    /**************/
    t.result = max(t.result, t.prefix);
    t.result = max(t.result, t.suffix);
    t.result = max(t.result, t.sum);
    /**************/
    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) ;
}


node update(int lo, int hi, int sp, int val)
{
    if(hi < idx || lo > idx)
    {
        node n ;
        return n ;
    }

    if(lo >= idx && hi <= idx)
    {
        node n(val) ;
        seg[sp] = n ;
        return seg[sp] ;
    }

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

    update(lo, mid, 2*sp + 1, val) ;
    update(mid + 1, hi, 2*sp + 2, val) ;

    seg[sp] = combineChild(seg[2*sp+1], seg[2*sp+2]) ;
    return seg[sp] ;
}



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, 0) ;

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

    while(M--)
    {
        int c ;
        scanf("%d",&c) ;

        if(c == 0)
        {
            int val ;
            scanf("%d %d", &idx, &val) ;
            idx -- ;

            update(0, N-1, 0, val) ;
        }
        else if(c == 1)
        {
            scanf("%d %d", &i, &j) ;
            i-- ;
            j-- ;
            int ans ;

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