//
// Created by 55062 on 2024/5/22.
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,a[500010];
struct node{
    ll l,r,sum,lnum,rnum,num;
}t[1000100];
void pushup(ll x){
    t[x].sum=t[x].sum+t[x].sum;
    t[x].lnum=max(t[x*2].lnum,t[x*2].sum+t[x*2+1].lnum);    
    t[x].rnum=max(t[x*2+1].rnum,t[x*2+1].sum+t[x*2].rnum);
    t[x].num=max({t[x].lnum,t[x].rnum,t[x*2].rnum+t[x*2+1].lnum});
}
void build(ll x,ll l,ll r){
    t[x].l=l,t[x].r=r;
    if(l==r){
        t[x].sum=t[x].lnum=t[x].rnum=t[x].num=a[l];
        return ;
    }ll mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
}
void update(ll x,ll l,ll r,ll pos,ll v){
    if(t[x].l==t[x].r){
        t[x].sum=t[x].lnum=t[x].rnum=t[x].num=v;
        return ;
    }ll mid=(l+r)/2;
    if(pos<=mid) update(x*2,l,mid,pos,v);
    else update(2*x+1,mid+1,r,pos,v);
    pushup(x);
}
node problem(ll x,ll l,ll r,ll L,ll R){
    if(L<=l&&r<=R) return t[x];
    ll mid=(l+r)/2;
    if(R<=mid) return problem(x*2,l,mid,L,R);
    if(L>mid) return problem(x*2+1,mid+1,r,L,R);
    node res,fl=problem(x*2,l,mid,L,R),fr=problem(x*2+1,mid+1,r,L,R);
    res.sum=fl.sum+fr.sum;
    res.lnum=max(fl.lnum,fl.sum+fr.lnum);
    res.rnum=max(fr.rnum,fr.sum+fl.rnum);
    res.num=max({res.lnum,res.rnum,fl.rnum+fr.lnum});
    return res;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        ll opt,x,y;
        cin>>opt>>x>>y;
        if(opt==2) update(1,1,n,x,y);
        else cout<<problem(1,1,n,x,y).num<<endl;
    }
}

AC #1 其他全部是TLE