AC on #1 code:

#include<bits/stdc++.h>
using namespace std;
//#define int  long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
	int vis=1,ans=0;
	char x=getchar();
	while(x<'0'||x>'9'){
		if(x=='-')vis=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9'){
		ans=ans*10+x-'0';
		x=getchar();
	}
	return vis*ans;
}
inline void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+'0');
}
const int N=5e5+90;
int n=read(),m=read();
int d[N];
struct node{
	int l,r,lsum,rsum,sum,len,ans;
}a[4*N];
inline void pushup(int p){
	a[p].len=a[p*2].len+a[p*2+1].len;
	a[p].sum=max(max(a[p*2].sum,a[p*2+1].sum),a[p*2].rsum+a[p*2+1].lsum);
	a[p].lsum=max(a[p*2].lsum,a[p*2].ans+a[p*2+1].lsum);
	a[p].rsum=max(a[p*2+1].rsum,a[p*2+1].ans+a[p*2].rsum);
	a[p].ans=a[p*2].ans+a[p*2+1].ans;
}
inline void bulid(int p,int l,int r){
	a[p].l=l,a[p].r=r,a[p].len=r-l+1;
	if(l==r){
		a[p].ans=a[p].lsum=a[p].rsum=a[p].sum=d[l];
		return;
	}
	int mid=(l+r)/2;
	bulid(p*2,l,mid);
	bulid(p*2+1,mid+1,r);
	pushup(p);
}
inline void modify(int p,int x,int v){
	if(x<a[p].l||a[p].r<x)return;
	if(a[p].l==x&&a[p].len==1){
		a[p].ans=a[p].lsum=a[p].rsum=a[p].sum=v;
		return;
	}
	int mid=(a[p].l+a[p].r)/2;
	if(x<=mid)modify(p*2,x,v);
	else modify(p*2+1,x,v);
	pushup(p);
}
inline int ask(int p,int l,int r){
	if(r<a[p].l||a[p].r<l)return INT_MIN;
	if(l<=a[p].l&&a[p].r<=r){
		return a[p].sum;
	}
	return max(ask(p*2,l,r),ask(p*2+1,l,r));
}
signed main(){
	for(int i=1;i<=n;i++){
		d[i]=read();
	}
	bulid(1,1,n);
	while(m--){
		int k=read(),l=read(),r=read();
		if(k==1){
			if(l>r)swap(l,r);
			print(ask(1,l,r)),endl;
		}else{
			modify(1,l,r);
		}
	}
	return 0;
}