Shared code

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
class SegmentTree
{
    
private:
    
    vector<pair<ll,ll> > seg;   //{sum,pref}
    
public:
    
    SegmentTree(ll n)
    {
        seg.resize(4*n+1);
    }
    
    void build(ll ind,ll lo,ll hi,vector<ll> &a)
    {
        if(lo==hi)
        {
            seg[ind].first=a[lo];
            seg[ind].second=a[lo];
            return ;
        }
        ll mid=lo+(hi-lo)/2;
        build(2*ind+1,lo,mid,a);
        build(2*ind+2,mid+1,hi,a);
        seg[ind].first=seg[2*ind+1].first+seg[2*ind+2].first;
        seg[ind].second=max(seg[2*ind+1].second,seg[2*ind+1].first+seg[2*ind+2].second);
    }
    
    void update(ll ind,ll lo,ll hi,ll i,ll val)
    {
        if(lo==hi)
        {
            seg[ind].first=val;
            seg[ind].second=val;
            return ;
        }
        ll mid=lo+(hi-lo)/2;
        if(i<=mid)
        {
            update(2*ind+1,lo,mid,i,val);
        }
        else
        {
            update(2*ind+2,mid+1,hi,i,val);
        }
        seg[ind].first=seg[2*ind+1].first+seg[2*ind+2].first;
        seg[ind].second=max(seg[2*ind+1].second,seg[2*ind+1].first+seg[2*ind+2].second);
    }
    
    pair<ll,ll> query(ll ind,ll lo,ll hi,ll l,ll r)
    {
        if(l>hi||lo>r)
        {
            return make_pair(0,INT_MIN);
        }
        if(l<=lo&&hi<=r)
        {
            return seg[ind];
        }
        ll mid=lo+(hi-lo)/2;
        pair<ll,ll> left=query(2*ind+1,lo,mid,l,r),right=query(2*ind+2,mid+1,hi,l,r);
        pair<ll,ll> ans=make_pair(left.first+right.first,max(left.second,left.first+right.second));
        return ans;
    }
    
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,q;
    cin>>n>>q;
    vector<ll> a(n);
    for(auto &v:a)
    {
        cin>>v;
    }
    SegmentTree st(n);
    st.build(0,0,n-1,a);
    while(q--)
    {
        ll type;
        cin>>type;
        if(type==1)
        {
            ll i,val;
            cin>>i>>val;
            st.update(0,0,n-1,i-1,val);
        }
        if(type==2)
        {
            ll l,r;
            cin>>l>>r;
            cout<<max((ll)0,st.query(0,0,n-1,l-1,r-1).second)<<endl;
        }
    }
    return 0;
}