Shared code

#include <bits/stdc++.h>
using namespace std;
#define trace(x) clog << "=>" << #x << ":" << x << endl;
#define trace2(x, y) clog << "=>" << #x << ":" << x << endl <<"=>"<<#y << ":" << y << endl;
using ll = long long int;
using pii = pair<ll, ll>;
int mod = 1e9 + 7;
ll exp(ll base, ll pw) { ll ans = 1; while (pw > 0) { if (pw & 1) { ans *= base; } base *= base; pw >>= 1; } return ans; }
int add(ll a, ll b){ return (a%mod + b%mod)%mod; }
int mul(ll a, ll b){ return (a%mod * b%mod)%mod; }
int modexp(int base, int pw) { int ans = 1; while (pw > 0) { if (pw & 1) { ans = mul(ans,base); } base = mul(base, base); pw >>= 1; } return ans; }

void build(vector<ll> &v, vector<pii> &seg, int i, int l, int r){

	//if leaf
	if(l == r){
		seg[i].first = max<ll>(0, v[l-1]);
		seg[i].second = v[l-1];
		return;
	}

	int mid = (r - l)/2 + l;

	build(v, seg, 2*i, l, mid);
	build(v, seg, 2*i+1, mid+1, r);
	// max{best_pre(left), sum(left) + best_pre(right)}
	seg[i].first = max<ll>(0, max<ll>(seg[2*i].first, seg[2*i].second + seg[2*i+1].first));
	seg[i].second = seg[2*i].second + seg[2*i+1].second;

}

void update(vector<pii> &seg, int i, int l, int r, ll pos, ll val){
	//if leaf
	if(l == r){
		if(l == pos){
			seg[i].first = seg[i].second = val;
		}
		return;
	}

	int mid = (r - l)/2 + l;

	update(seg, 2*i, l, mid, pos, val);
	update(seg, 2*i+1, mid+1, r, pos, val);

	// max{best_pre(left), sum(left) + best_pre(right)}
	seg[i].first = max<ll>(0, max<ll>(seg[2*i].first, seg[2*i].second + seg[2*i+1].first));
	seg[i].second = seg[2*i].second + seg[2*i+1].second;

}

pii query(vector<pii> &seg, int i, int l, int r, int ql, int qr){
	//ql....qr  l....r || l....r ql...qr
 	if(qr < l || r < ql)return {0, 0};
 	//ql.....l,r.....qr
 	if(l >= ql && r <= qr)return seg[i];

 	int mid = (r-l)/2 + l;

 	pii left  = query(seg, 2*i, l, mid, ql, qr);
 	pii right = query(seg, 2*i+1, mid+1, r, ql, qr) ;

 	ll best_pre = max<ll>(0, max<ll>(left.first, left.second+right.first));
 	ll sum = left.second + right.second;

 	return {best_pre, sum};

}

void solve(){
	int n, q;
	cin>>n>>q;
	vector<ll> v(n);
	for(int i=0; i<n; i++)cin>>v[i];
 	vector<pii> seg(4*n+1);
	build(v, seg, 1, 1, n);

	for(int i=1; i<=q; i++){
		int type;
		cin>>type;
		if(type == 1){
			ll pos, val;
			cin>>pos>>val;
			update(seg, 1, 1, n, pos, val);
		}else{
			int a, b;
			cin>>a>>b;
			cout<<query(seg, 1, 1, n, a, b).first<<"\n";
		}
	}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
    int t;
    t = 1;
    while(t--){
    	solve();
    }
    return 0;
}