#include<algorithm>
#include<cstdio>
using namespace std;

const int N=500001;

struct NODE
{
	int sum;
	int maxl;
	int maxr;
	int ans;//最大子段和 
}node[N<<2];

int n,m;

inline void data(NODE &u,const NODE &ls,const NODE &rs)
{
	u.sum=ls.sum+rs.sum;
	
	u.maxl=max(ls.maxl,ls.sum+rs.maxl);
	u.maxr=max(rs.maxr,rs.sum+ls.maxr);
	
	u.ans=max( ls.maxr+rs.maxl , max( ls.ans , rs.ans ) );
}

void build(int u,int l,int r)
{
	if(l==r)
	{
		scanf("%d",&node[u].sum);
		node[u].maxr=node[u].maxl=node[u].ans=node[u].sum;
		return;
	}
	
	int mid=(l+r)/2;
	
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	data(node[u],node[u<<1],node[u<<1|1]);
}

NODE query(int u,int l,int r,int a,int b)
{
	if(a<=l && r<=b)
	{
		return node[u];
	}
	int mid=(l+r)/2;
	
	if(a<=mid && mid<b)
	{
		NODE res;
		data(res,query(u<<1,l,mid,a,b) ,query(u<<1|1,mid+1,r,a,b)); 
		return res;
	}
	else if(a<=mid)
		return query(u<<1,l,mid,a,b);
	else 
		return query(u<<1|1,mid+1,r,a,b);
}

void update(int u,int l,int r,int pos,int key)
{
	if(l==r)
	{
		node[u].ans=node[u].maxl=node[u].maxr=node[u].sum=key;
		return ;
	}
	
	int mid=(l+r)/2;
	
	if(pos<=mid)//左半边 
	{
		update(u<<1,l,mid,pos,key);
	}
	else
	{
		update(u<<1|1,mid+1,r,pos,key);
	}
	
	data(node[u],node[u<<1],node[u<<1|1]);
}

int main()
{
	scanf("%d%d",&n,&m);
	build(1,1,n);
	
	int op;  int a,b;
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			if(a>b)
				swap(a,b);
			scanf("%d%d",&a,&b);
			printf("%d\n",query(1,1,n,a,b).ans);
		}
		else if(op==2)
		{
			scanf("%d%d",&a,&b);
			update(1,1,n,a,b);
		}
	}
	return 0;
}