KGSS - Maximum Sum

#include <bits/stdc++.h>
#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 max3(a,b,c) max(a , max(b,c))

#define mx 100005
using namespace std;


class node
{
public:
    int first ;
    int second ;

    node(int tem)
    {
        first = tem ;
        second = -1 ;
    }
    node()
    {
        first = second = -1 ;
    }
};

int A[mx] ;
node seg[3*mx] ;
int i, j, idx ;

node combineChild(node a, node b)
{
    node t ;
    t.first = max(a.first, b.first) ;


    if(t.first == a.first)
    {
        t.second = max3(a.second, b.first, b.second) ;
    }
    else
    {
        t.second = max3(a.second, a.first, b.second) ;
    }
    return t ;
}


node build(int lo, int hi, int sp)
{
    if(lo == hi)
    {
        node n(A[lo]) ;
        seg[sp] = n ;
        return seg[sp] ;
    }
    int mid ;
    mid = (lo + hi) / 2 ;

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

    seg[sp] = combineChild(l,r) ;
    return seg[sp] ;
}


node query(int lo, int hi, int sp)
{
    if(lo > j || hi < i)
    {
        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(lo > idx || hi < 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()
{
//    fi ;
    int N ;
    scanf("%d",&N) ;

    for(int i = 0 ; i < N ; i++)
    {
        scanf("%d",&A[i]) ;
    }
    build(0 , N-1 , 0);
    int Q ;
    scanf("%d",&Q) ;
    while(Q--)
    {
        char c ;
        scanf(" %c",&c) ;
        if(c == 'Q')
        {
            scanf("%d %d",&i, &j) ;
            i-- ;
            j-- ;
            node n ;
            n = query(0, N-1, 0) ;
            int ans ;
//            cout << n.first  << " " << n.second << endl ;
            ans = n.first + n.second ;
            printf("%d\n",ans);
        }
        else if(c == 'U')
        {
            int value ;
            scanf("%d %d",&idx, &value) ;
            idx-- ;
            update(0, N-1, 0, value) ;
        }
    }
    return 0 ;
}