#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
struct Node{
    int left,right;
    int sum,val;
    int lv,rv;
}t[maxn*4];
int n,q,a[maxn];
void pushup(int u){
    int ls=u*2,rs=u*2+1;
    t[u].sum=t[ls].sum+t[rs].sum;
    t[u].val=max(t[ls].rv+t[rs].lv,max(t[ls].val,t[rs].val));
    t[u].lv=max(t[ls].lv,t[rs].lv+t[ls].sum);
    t[u].rv=max(t[rs].rv,t[ls].rv+t[rs].sum);
    return;
}
Node merge(Node a, Node b){
    Node res;
    res.sum = a.sum + b.sum;
    res.lv = max(a.lv, a.sum + b.lv);
    res.rv = max(b.rv, b.sum + a.rv);
    res.val = max(max(a.val, b.val), a.rv + b.lv);
    return res;
}
void build(int u,int L,int R){
    t[u].left=L;
    t[u].right=R;
    if(L==R){
        t[u].sum=a[L];
        t[u].val=a[L];
        t[u].lv=t[u].rv=a[L];
    }else{
        int M=(L+R)>>1;
        build(u*2,L,M);
        build(u*2+1,M+1,R);
        pushup(u);
    }
    return;
}
bool inr(int L,int R,int l,int r){
    return L>=l&&R<=r;
}
bool otr(int L,int R,int l,int r){
    return R<l||L>r;
}
void update(int u,int k,int d){
    if(t[u].left==t[u].right){
        t[u].sum=d;
        t[u].val=d;
        t[u].lv=t[u].rv=d;
    }else{
        if(k>=t[u*2].left&&k<=t[u*2].right) update(u*2,k,d);
        else update(u*2+1,k,d);
        pushup(u);
    }
    return;
}
Node query(int u,int l,int r){
    if(l<=t[u].left && t[u].right<=r){
        return t[u];
    }
    int mid=(t[u].left+t[u].right)>>1;
    if(r<=mid) return query(u*2,l,r);
    if(l>mid) return query(u*2+1,l,r);
    return merge(query(u*2,l,r), query(u*2+1,l,r));
}
int main(){
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,1,n);
    while(q--){
        int op;
        cin >> op;
        if(op==1){
            int l,r;
            cin >> l >> r;
            Node res = query(1,l,r);
            cout << res.val << endl;
        }else{
            int p,s;
            cin >> p >> s;
            update(1,p,s);
        }
    }
    return 0;
}