// #include <bits/stdc++.h>
// using namespace std;
// const int N = 1e6 + 10, mod = 998244353;
// const double eps = 1e-6; // 解决精度的问题,代表0,因为c++浮点数的原因,我们将小于1e-6的数看成0
// const int inf = 0x3f3f3f3f;
// const double M = 3.14159265358979;
// #define lowbit(x) x & -x
// #define pb push_back
// #define endl '\n'
// #define mem(a, b) memset(a, b, sizeof a)
// #define lu u << 1 // u的左儿子2*u
// #define ru u << 1 | 1 // u的右儿子2*u+1
// #define bug1(x) cout << x << endl
// #define bug2(x, y) cout << x << ' ' << y << endl
// #define bug3(x, y, z) cout << x << ' ' << y << ' ' << z << endl
// #define int long long
// #define xx first // 宏定义
// #define yy second // 宏定义
// typedef pair<int, int> PII;
// using ll = long long;
// // typedef unsigned long long ull;
// // typedef long long ll;
// int n, q;
// int l, r;
// int x, y;
// int a[N];
// struct node
// {
// int l, r;
// int sum;
// int lmax, rmax, tmax;
// } tr[N << 2];
// void pushup(node &u, node &ls, node &rs)
// {
// u.sum = ls.sum + rs.sum;
// u.lmax = max(ls.lmax, ls.sum + rs.lmax);
// u.rmax = max(rs.rmax, rs.sum + ls.rmax);
// u.tmax = max({ls.tmax, rs.tmax, ls.rmax + rs.lmax});
// }
// void pushup(int u)
// {
// pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
// }
// void build(int u, int l, int r)
// {
// tr[u] = {l, r};
// if (l == r)
// {
// tr[u] = {l, r, a[l], a[l], a[l], a[l]};
// return;
// }
// int mid = l + r >> 1;
// build(u << 1, l, mid);
// build(u << 1 | 1, mid + 1, r);
// pushup(u);
// }
// void modify(int u, int x, int k)
// {
// if (tr[u].l == tr[u].r)
// {
// tr[u] = {x, x, k, k, k, k};
// return;
// }
// int mid = tr[u].l + tr[u].r >> 1;
// if (x <= mid)
// modify(u << 1, x, k);
// else
// modify(u << 1 | 1, x, k);
// pushup(u); //!!!!!记得自底向上更新信息
// }
// node query(int u, int l, int r)
// {
// if (tr[u].l >= l && tr[u].r <= r)
// return tr[u];
// int mid = tr[u].l + tr[u].r >> 1;
// if (l > mid)
// return query(u << 1 | 1, l, r);
// else if (r <= mid)
// return query(u << 1, l, r);
// else
// {
// node left = query(u << 1, l, r);
// node right = query(u << 1 | 1, l, r);
// node res;
// pushup(res, left, right);
// return res;
// }
// }
// signed main()
// {
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
// cin >> n >> q;
// for (int i = 1; i <= n; i++)
// cin >> a[i];
// build(1, 1, n);
// while (q--)
// {
// int op;
// cin >> op;
// if (op == 1)
// {
// cin >> l >> r;
// if (l > r)
// swap(l, r);
// node res = query(1, l, r);
// cout << res.tmax << '\n';
// }
// else
// {
// cin >> x >> y;
// modify(1, x, y);
// }
// }
// return 0;
// }
//自己动手写成版
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int n, q;
int a[N];
int l, r;
int x, k;
struct node
{
int l, r;
int sum;
int lmax, rmax, tmax;
} tr[N << 2];
void pushup(node &u, node &ls, node &rs)
{
u.sum = ls.sum + rs.sum;
u.lmax = max(ls.lmax, ls.sum + rs.lmax);
u.rmax = max(rs.rmax, rs.sum + ls.rmax);
u.tmax = max({ls.tmax, rs.tmax, ls.rmax + rs.lmax});
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r)
{
tr[u] = {l, r, a[l], a[l], a[l], a[l]};
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int k)
{
if (tr[u].l == tr[u].r)
{
tr[u] = {x, x, k, k, k, k};
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x > mid) // 大于mid就是>mid, 但是小于mid就是<=mid;(一种潜规则???)
modify(u << 1 | 1, x, k);
else
modify(u << 1, x, k);
pushup(u);
}
node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (l > mid) // 大于mid就是>mid, 但是小于mid就是<=mid;(一种潜规则???)
return query(u << 1 | 1, l, r);
else if (r <= mid) // 大于mid就是>mid, 但是小于mid就是<=mid;(一种潜规则???)
return query(u << 1, l, r);
else
{
node left = query(u << 1, l, r);
node right = query(u << 1 | 1, l, r);
node res;
pushup(res, left, right);
return res;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
cin >> l >> r;
if (l > r)
swap(l, r);
node res = query(1, l, r);
cout << res.tmax << '\n';
}
else
{
cin >> x >> k;
modify(1, x, k);
}
}
return 0;
}