都是线段树，第一个：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

long long n,m;
long long a[500010];
struct node{
	long long mv,ml,mr,sum;
}tr[2000010];

inline void pushup(node &nv,const node &ls,const node &rs) {
	if(ls.mr > 0 && rs.ml > 0) nv.mv = ls.mr + rs.ml;
	else nv.mv = max(ls.mr,rs.ml);
	nv.mv = max(nv.mv,ls.mv);
	nv.mv = max(nv.mv,rs.mv);
	nv.ml = max(ls.ml,ls.sum + rs.ml);
	nv.mr = max(rs.mr,rs.sum + ls.mr);
	nv.sum = ls.sum + rs.sum;
}

void build(long long k,long long l,long long r) {
	if(l == r) {
		tr[k].sum = tr[k].mv = tr[k].ml = tr[k].mr = a[l];
		return;
	}
	long long mid = l+r>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	pushup(tr[k],tr[k*2],tr[k*2+1]);
}

void change(long long k,long long l,long long r,long long j,long long v) {
	if(l > j || r < j) return;
	if(l == r && l == j) {
		a[l] = v;
		tr[k].sum = tr[k].mv = tr[k].ml = tr[k].mr = v;
		return;
	}
	long long mid = l+r>>1;
	change(k*2,l,mid,j,v);
	change(k*2+1,mid+1,r,j,v);
	pushup(tr[k],tr[k*2],tr[k*2+1]);
}

node query(long long k,long long l,long long r,long long x,long long y) {
	if(l > y || r < x) {
		node res;
		res.mv = -0x3ffffff;
		res.ml = -0x3ffffff;
		res.mr = -0x3ffffff;
		res.sum = tr[k].sum;
		return res;
	}
	if(l >= x && r <= y) return tr[k];
	long long mid = l+r>>1;
	node res;
	if(x <= mid && y >= mid) {
		pushup(res,query(k*2,l,mid,x,y),query(k*2+1,mid+1,r,x,y));
		return res;
	}
	else if(mid >= y) res = query(k*2,l,mid,x,y);
	else res = query(k*2+1,mid+1,r,x,y);
	
	return res;
}

int main() {
	cin >> n >> m;
	for(long long i = 1;i <= n;i++) cin >> a[i];
	build(1,1,n);
	
	for(long long i = 1;i <= m;i++) {
		long long k,l,r;
		cin >> k >> l >> r;
		if(k == 2) {
			change(1,1,n,l,r);
		}
		else {
			if(l > r) swap(l,r);
			cout << query(1,1,n,l,r).mv << endl;
		}
	}
	
	return 0;
}

第二个：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

long long n,m;
long long a[500010],sum[2000010],maxv[2000010],maxl[2000010],maxr[2000010];
struct node{
	long long mv,ml,mr,sum;
};

void build(long long k,long long l,long long r) {
	if(l == r) {
		sum[k] = a[l];
		return;
	}
	long long mid = l+r>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	sum[k] = sum[k*2] + sum[k*2+1];
}

void change(long long k,long long l,long long r,long long j,long long v) {
	if(l > j || r < j) return;
	if(l == r && l == j) {
		a[l] = v;
		sum[k] = v;
		return;
	}
	long long mid = l+r>>1;
	change(k*2,l,mid,j,v);
	change(k*2+1,mid+1,r,j,v);
	sum[k] = sum[k*2] + sum[k*2+1];
}

void update(long long k,long long l,long long r) {
	if(l == r) {
		maxv[k] = a[l];
		maxl[k] = a[l];
		maxr[k] = a[l];
		return;
	}
	long long mid = l+r>>1;
	update(k*2,l,mid);
	update(k*2+1,mid+1,r);
	if(maxr[k*2] > 0 && maxl[k*2+1] > 0) maxv[k] = maxr[k*2] + maxl[k*2+1];
	else maxv[k] = max(maxr[k*2],maxl[k*2+1]);
	maxv[k] = max(maxv[k],maxv[k*2]);
	maxv[k] = max(maxv[k],maxv[k*2+1]);
	maxl[k] = max(maxl[k*2],sum[k*2] + maxl[k*2+1]);
	maxr[k] = max(maxr[k*2+1],sum[k*2+1] + maxr[k*2]);
}

node query(long long k,long long l,long long r,long long x,long long y) {
	if(l > y || r < x) {
		node res;
		res.mv = -0x3ffffff;
		res.ml = -0x3ffffff;
		res.mr = -0x3ffffff;
		res.sum = sum[k];
		return res;
	}
	if(l >= x && r <= y) {
		node res;
		res.sum = sum[k];
		res.mv = maxv[k];
		res.ml = maxl[k];
		res.mr = maxr[k];
		return res;
	}
	long long mid = l+r>>1;
	node res;
	if(x <= mid && y >= mid) {
		node ls = query(k*2,l,mid,x,y);
		node rs = query(k*2+1,mid+1,r,x,y);
		if(ls.mr > 0 && rs.ml > 0) res.mv = ls.mr + rs.ml;
		else res.mv = max(ls.mr,rs.ml);
		res.mv = max(res.mv,ls.mv);
		res.mv = max(res.mv,rs.mv);
		res.ml = max(ls.ml,ls.sum + rs.ml);
		res.mr = max(rs.mr,rs.sum + ls.mr);
		res.sum = ls.sum + rs.sum;
		return res;
	}
	else if(mid >= y) res = query(k*2,l,mid,x,y);
	else res = query(k*2+1,mid+1,r,x,y);
	
	return res;
}

int main() {
	cin >> n >> m;
	for(long long i = 1;i <= n;i++) cin >> a[i];
	build(1,1,n);
	update(1,1,n);
	
	for(long long i = 1;i <= m;i++) {
		long long k,l,r;
		cin >> k >> l >> r;
		if(k == 2) {
			change(1,1,n,l,r);
			update(1,1,n);
		}
		else {
            if(l > r) swap(l,r);
			cout << query(1,1,n,l,r).mv << endl;
		}
	}
	
	return 0;
}

我感觉都是O(mlogn)的复杂度，但是第二个代码就超时了