线段树经典题。

考虑由左右两个区间子区间$tl,tr$得到当前区间的最大子段和$ans$，则有
$$ans=max\text{{tl的最大子段和，tr的最大子段和，跨越区间中点的最大子段和}}$$

tl的最大子段和&tr的最大子段和递归求即可。
跨越中点的的最大子段和=tl右端点起的向左的最大子段和+tr左端点起的向右的最大子段和

所以线段树上每个节点维护四个信息：
1. ml:左端点起的向右的最大子段和
2. mr:右端点起的向左的最大子段和
3. mx整个区间的最大子段和
4. sum:区间和

然后pushup时这四个信息都更新一下即可.

另外，由于当时我不理解如何查询，所以再解释一下：
查询的返回值是一个结构体(也就是类似线段树上的一个节点),真正的最大子段和是返回值.mx
- 如果当前区间被要查询区间完全包含，返回当前区间的信息
- 如果要查询的区间只在当前区间的左区间，向左区间查询
- 如果要查询的区间只在当前区间的右区间，向右区间查询
- 其他情况，像pushup那样合并左右区间的查询结果，并返回

总时间复杂度$O(nlogn)$

//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

typedef long long ll;
typedef std::pair<ll,ll> pll;
#define INF (1ll<<58)
ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
ll min(ll a,ll b)
{
    return a<b?a:b;
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}
bool umin(ll &a,ll b)
{
    if(b<a)return a=b,1;
    return 0;
}
bool umax(ll &a,ll b)
{
    if(b>a)return a=b,1;
    return 0;
}
ll abs(ll x)
{
    return x>0?x:-x;
}
/**********/

#define MAXN 500011
ll n,m;
struct Segment_Tree
{
    struct node
    {
        ll sum,ml,mr,mx;
        void operator =(ll k)
        {
            sum=ml=mr=mx=k;
        }
        node()
        {
            sum=ml=mr=mx=0;
        }
    }t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
    typedef unsigned un;
    node pushup(node _tl,node _tr)
    {
        node _rt;
        _rt.sum=_tl.sum+_tr.sum;
        _rt.ml=max(_tl.ml,_tl.sum+_tr.ml);
        _rt.mr=max(_tr.mr,_tr.sum+_tl.mr);
        _rt.mx=max(_tl.mr+_tr.ml,max(_tl.mx,_tr.mx));
        return _rt;
    }
    void build(un l=1,un r=n,un num=1)
    {
        if(l==r)rt=read();
        else
        {
            un mid=(l+r)>>1;
            build(l,mid,num<<1);
            build(mid+1,r,num<<1|1);
            rt=pushup(tl,tr);
        }
    }
    void modify(un x,ll k,un l=1,un r=n,un num=1)
    {
        if(l==r)
        {
            if(l==x)rt=k;
            return;
        }
        un mid=(l+r)>>1;
        if(x<=mid)modify(x,k,l,mid,num<<1);
        if(x>mid)modify(x,k,mid+1,r,num<<1|1);
        rt=pushup(tl,tr);
    }
    node query(un ql,un qr,un l=1,un r=n,un num=1)
    {
       if(ql<=l&&r<=qr)return rt;
       un mid=(l+r)>>1;
       if(qr<=mid)return query(ql,qr,l,mid,num<<1);
       if(ql>mid)return query(ql,qr,mid+1,r,num<<1|1);
       return pushup(query(ql,qr,l,mid,num<<1),query(ql,qr,mid+1,r,num<<1|1));
    }
}sgt;

int main()
{
    n=read(),m=read();
    sgt.build();
    for(ll i=1;i<=m;++i)
    {
        ll op=read();
        if(op==1)
        {
            ll l=read(),r=read();
            if(l>r)std::swap(l,r);
            printf("%lld\n",sgt.query(l,r).mx);
        }
        else
        {
            ll x=read(),k=read();
            sgt.modify(x,k);
        }
    }
    return 0;
}