对于一个固定区间，求最大子段和我们有O(n)
的算法。但是如何维护不同区间的LIS
就成了一个问题。我们选择线段树解决区间问题，但使用线段树的话，我们需要明白，维护什么值，以及如何进行区间操作。

那么我们思考，对于相邻的两个区间，他们的LIS
有几种可能？
1. 左侧区间的LIS

1. 右侧区间的LIS

2. 两个区间合并后，中间新连接的部分
   前两点都好理解，针对第三点我们继续思考，中间部分能够成为LIS
   ，其实就是我们从连接部分分别向前向后，获得一个尽可能大的前/后缀和。那么我们维护或者合并区间的LIS
   就需要维护三个值，区间最大子段和，最大前缀和，最大后缀和。而我们在合并区间的时候，如何维护前/后缀和呢？我们需要多维护一个区间和。

整理我们得到，定义区间ls,rs
合并得到区间d，每个区间维护区间和sum
，区间最大字段和dat
，区间最大前缀和lmax
，区间最大后缀和rmax
。则合并区间时，可得关系如下
1. d.sum=ls.sum+rs.sum

1. d.dat=max(ls.dat,rs.dat,ls.rmax+rs.lmax)

2. d.lmax=max(ls.lmax,ls.sum+rs.lmax)

3. d.rmax=max(rs.rmax,rs.sum+ls.rmax)

用线段树维护即可

include[HTML_REMOVED]

include[HTML_REMOVED]

define lson l,m,rt<<1

define rson m+1,r,rt<<1|1

using namespace std;
typedef long long ll;
const int N=500001;
ll maxn(ll a,ll b,ll c )
{
if(a>=b&&a>=c)
return a;
if(b>=a&&b>=c)
return b;
if(c>=a&&c>=b)
return c;
}
struct Node{
int l,r;
ll lmax,rmax,sum,dat;
int mid()
{
return (l+r)>>1;
}
}tree[N<<2];
void pushup(int rt)
{
tree[rt].lmax=maxn(tree[rt<<1].sum,tree[rt<<1].sum+tree[rt<<1|1].lmax,tree[rt<<1].lmax);
tree[rt].rmax=maxn(tree[rt<<1|1].sum,tree[rt<<1|1].sum+tree[rt<<1].rmax,tree[rt<<1|1].rmax);
tree[rt].dat=maxn(tree[rt<<1].dat,tree[rt<<1|1].dat,tree[rt<<1].rmax+tree[rt<<1|1].lmax);
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}

void build(int l,int r,int rt)
{
tree[rt].l=l;
tree[rt].r=r;

if(l==r)
{
    scanf("%lld",&tree[rt].dat);
    tree[rt].sum=tree[rt].lmax=tree[rt].rmax=tree[rt].dat;

    return;
}
int m=tree[rt].mid();
build(lson);
build(rson);
pushup(rt);

}
void update(int rt,int x,int y )
{
if(tree[rt].l==tree[rt].r)
{

    tree[rt].sum=tree[rt].lmax=tree[rt].rmax=tree[rt].dat=y;
    return;
}
int m=tree[rt].mid();
if(x<=m) update(rt<<1,x,y);
else update(rt<<1|1,x,y);
pushup(rt);

}
Node query(int rt, int l, int r){
if(tree[rt].l==l && tree[rt].r==r)
{
return tree[rt];
}

int m = tree[rt].mid();
if(m >= r)
    return query(rt<<1, l, r);
else if(m < l)
    return query(rt<<1|1, l, r);
else {
    Node ls = query(lson);
    Node rs = query(rson);
    Node ans;
    ans.dat = maxn(ls.dat, rs.dat, ls.rmax+rs.lmax);
    ans.lmax = maxn(ls.sum,ls.lmax, ls.sum+rs.lmax);
    ans.rmax = maxn(rs.sum,rs.rmax, rs.sum+ls.rmax);
    ans.sum  = ls.sum + rs.sum;

    return ans;
}

}

int main()
{
int n,m;
cin>>n>>m;
build(1,n,1);
int i;int j,t;

for(i=0;i<m;i++)
{
    scanf("%d",&j);
    if(j==1)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        if(a>b)
        {
            swap(a,b);
        }

        Node ans=query(1,a,b);
        cout<<ans.dat<<endl;

    }
    else
    {
        int x,y;
        scanf("%d %d",&x,&y);
        update(1,x,y);
    }
}

}