SPOJ GSS3

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

struct Node {
    ll sum;
    ll prefix;
    ll suffix;
    ll ans;
};

Node combine(Node l, Node r) {
    Node ret;
    ret.sum = l.sum + r.sum;
    ret.prefix = max(l.prefix,l.sum+r.prefix);
    ret.suffix = max(r.suffix,r.sum+l.suffix);
    ret.ans = max(ret.sum,max(ret.prefix,max(ret.suffix,max(l.ans,max(r.ans,l.suffix+r.prefix)))));
    return ret;
}

ll arr[50001];
Node tree[4*50001];
int n;

void build(int l = 1, int r = n, int p = 1) {
    if(l == r) {
        tree[p].sum = tree[p].prefix = tree[p].suffix = tree[p].ans =  arr[l];
    }
    else {
        int mid = (l+r)/2;
        build(l,mid,p*2);
        build(mid+1,r,p*2+1);
        tree[p] = combine(tree[p*2],tree[p*2+1]);
    }
}

Node query(int ql, int qr,int l = 1, int r = n, int p = 1) {
    if(l >= ql && r <= qr) {
        return tree[p];
    }
    int mid = (l+r)/2;
    if(ql <= mid && qr >= mid+1)
        return combine(query(ql,min(qr,mid),l,mid,p*2),query(max(ql,mid+1),qr,mid+1,r,p*2+1));
    if(ql <= mid)
        return query(ql,qr,l,mid,p*2);
    return query(ql,qr,mid+1,r,p*2+1);
}

void update(int qt, ll v, int l = 1, int r = n, int p = 1) {
    if(l == r) {
        arr[l] = v;
        tree[p].sum = tree[p].prefix = tree[p].suffix = tree[p].ans =  arr[l];
    }
    else {
        int mid = (l+r)/2;
        if(qt <= mid) {
            update(qt,v,l,mid,p*2);
        }
        else {
            update(qt,v,mid+1,r,p*2+1);
        }
        tree[p] = combine(tree[p*2],tree[p*2+1]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    build();
    int q;
    cin >> q;
    while(q--) {
        int t,x,y;
        cin >> t >> x >> y;
        if(t) {
            cout << query(x,y).ans << "\n";
        }
        else {
            update(x,y);
        }
    }
    return 0;
}