#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int n,m;

struct segment_tree
{
	int l, r;
	int lm, rm;
	int sum, tmax;
}t[N * 4];

void push_up (int u)
{
	t[u].lm = max (t[2 * n].lm, t[2 * n].sum + t[2 * n].lm);
	t[u].rm = max (t[2 * n + 1].rm, t[2 * n].sum + t[2 * n].rm);
	t[u].sum = t[2 * n].sum + t[2 * n + 1].sum;
	t[u].tmax = max (max (t[2 * n].tmax, t[2 * n + 1].tmax), t[2 * n].rm + t[2 * n + 1].lm);
}

void build (int u, int l, int r)
{
	t[u].l = l, t[u].r = r;
	if (l == r)
	{
		scanf ("%d ", &t[u].sum);
		t[u].lm = t[u].rm = t[u].tmax = t[u].sum;
		return ;
	}
	int mid = l + r >> 1;
	build (2 * u, l, mid);
	build (2 * u + 1, mid + 1, r);
	push_up (u);
}

void modify (int u, int x, int v)
{
	if (t[u].l == t[u].r and t[u].l == x)
	{
		t[u].lm = t[u].rm = t[u].tmax = t[u].sum = v;
		return ;
	}
	int mid = t[u].l + t[u].r >> 1;
	if (x <= mid)
		modify (2 * u, x, v);
	else
		modify (2 * u + 1, x, v);
	push_up (u);
}

segment_tree query (int u, int l, int r)
{
	if (t[u].l >= l and t[u].r <= r)
		return t[u];
	int mid = t[u].l + t[u].r >> 1;
	if (r <= mid)
		return query (2 * u,l,r);
	else if (l > mid)
		return query (2 * u + 1, l, r);
	else
	{
		segment_tree tr, t1 = query (2 * u, l, r), t2 = query (2 * u + 1, l, r);
		tr.lm = max (t1.lm, t1.sum + t2.lm);
		tr.rm = max (t2.rm, t1.rm + t2.lm);
		tr.tmax = max (max (t1.tmax, t2.tmax), t1.rm + t2.lm);
		return tr;
	}
}

int main ()
{
	scanf ("%d %d", &n, &m);
	build (1, 1, n);
	for (int i = 1; i <= m; ++ i)
	{
		int op, a, b;
		scanf ("%d %d %d", &op, &a, &b);
		if (a > b)
			swap (a, b);
		if (op == 1)
			printf ("%d\n", query (1, a, b));
		else
			modify (1, a, b);
	}
	return 0;
}