SPOJ - GSS3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e9;
struct Segment {
    long long sum, maxPre, maxSuf, maxSum;
    Segment operator + (const Segment &s2) const {
        Segment s;
        s.sum = sum + s2.sum;
        s.maxPre = max(maxPre, sum + s2.maxPre);
        s.maxSuf = max(s2.maxSuf, s2.sum + maxSuf);
        s.maxSum = max({maxSum, s2.maxSum, maxSuf + s2.maxPre});
        return s;
    }
    Segment () {
        sum = 0;
        maxSum = maxPre = maxSuf = -INF;
    }
    Segment (int x) {
        maxSum = maxPre = maxSuf = sum = x;
    }
};

const int MX = 50000;
int a[1+MX];
Segment tree[1+4*MX];
int n, m;
void update(int i) {
    tree[m+i] = Segment(a[i]);
    for (i += m; i > 1; i >>= 1) {
        int x = i, y = i^1;
        if (x > y) swap(x, y);
        tree[i>>1] = tree[x] + tree[y];
    }
}
Segment query(int ql, int qr, int cur = 1, int l = 0, int r = m) {
    if (qr <= l || r <= ql || cur >= m+n) return {};
    if (ql <= l && r <= qr) return tree[cur];
    return query(ql, qr, 2*cur, l, (l+r)/2) + query(ql, qr, 2*cur+1, (l+r)/2, r);
}

int main() {
    cin >> n;
    for (m = 1; m < n; m <<= 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        update(i);
    }
    int q; cin >> q;
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 0) a[x-1] = y, update(x-1);
        else cout << query(x-1, y).maxSum << endl;
    }
    return 0;
}