MaxQ ONI XI 2007

#include <fstream>
using namespace std;
ifstream cin("maxq.in");
ofstream cout("maxq.out");
typedef long long ll;
const ll mxN = 2e5;
ll sol , suf;
struct node{ll totalSum,bigSum, prefix, suffix;}A[4*mxN+1];
void build(int node, int st, int dr)
{
    if(st == dr)
    {
        int x; cin >> x;
        A[node] = {x,x,x,x};
        return;
    }
    int mid = (st + dr) / 2;
    build(2*node,st,mid);
    build(2*node+1,mid+1,dr);

    A[node].totalSum = A[2*node].totalSum + A[2*node+1].totalSum;
    A[node].prefix = max(A[2*node].prefix , A[2*node].totalSum + A[2*node+1].prefix);
    A[node].suffix = max(A[2*node+1].suffix, A[2*node+1].totalSum + A[2*node].suffix);
    A[node].bigSum = max(A[2*node].bigSum, A[2*node+1].bigSum);
    A[node].bigSum = max(A[node].bigSum, A[2*node].suffix + A[2*node+1].prefix);
}
void update(int node,int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        A[node] = {val,val,val,val};
        return;
    }
    int mid = (st + dr) / 2;
    if(poz <= mid)
        update(2*node,st,mid,poz,val);
    if(poz > mid)
        update(2*node+1,mid+1,dr,poz,val);
    A[node].totalSum = A[2*node].totalSum + A[2*node+1].totalSum;
    A[node].prefix = max(A[2*node].prefix , A[2*node].totalSum + A[2*node+1].prefix);
    A[node].suffix = max(A[2*node+1].suffix, A[2*node+1].totalSum + A[2*node].suffix);
    A[node].bigSum = max(A[2*node].bigSum, A[2*node+1].bigSum);
    A[node].bigSum = max(A[node].bigSum, A[2*node].suffix + A[2*node+1].prefix);
}
void query(int node, int st, int dr, int a, int b)
{
    if(a <= st && dr <= b)
    {
        sol = max(sol, A[node].bigSum);
        sol = max(sol,suf + A[node].prefix);
        suf = max(A[node].suffix, A[node].totalSum + suf);
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        query(2*node,st,mid,a,b);
    if(b > mid)
        query(2*node+1,mid+1,dr,a,b);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    build(1,1,n);
    int m;
    cin >> m;
    for(int i = 1;i<=m;i++)
    {
        int op, a, b;
        cin >> op >> a >> b;
        if(op == 0)
        {
            a++;
            update(1,1,n,a,b);
        }
        if(op == 1)
        {
            a++, b++;
            sol = suf = -1e18;
            query(1,1,n,a,b);
            cout << max(sol,0LL) << '\n';
        }
    }
    return 0;
}