题目描述：

$在小新家附近有一条“公园路”，路的一边从南到北依次排着 n公园。$

$一开始，小白就根据公园的风景给每个公园打了分。小新为了省事，每$

$次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之$

$间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园$

$的分数总和尽量高咯。同时，由于一些#园的景观会有所改变，所以，小白的$

$打分也可能会有一些变化。$

$那么，就请你来帮小白选择公园吧。$

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define re register
const int N = 1e7 + 1;
struct Tree{
    ll l;
    ll r;
    ll sum;
    ll maxx;
}tree[N];
ll n, m, a[N];
inline ll read()
{
    char c = getchar();
    ll f = 1,x = 0;
    while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
    return x * f;
}
inline Tree add(Tree x, Tree y){
    Tree c;
    c.sum = x.sum + y.sum;
    c.l = max(x.l, x.sum + y.l);
    c.r = max(y.r, y.sum + x.r);
    c.maxx = max(max(x.maxx, y.maxx), x.r + y.l);
    return c;
}
inline void build(ll k, ll l, ll r){
    if(l == r){
        tree[k].sum = a[l];
        tree[k].l = a[l];
        tree[k].r = a[l];
        tree[k].maxx = a[l];
        return ;
    }
    ll mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    tree[k] = add(tree[k << 1], tree[k << 1 | 1]);
}
inline Tree ask(ll k, ll x, ll y, ll l, ll r){
    if(x <= l && r <= y) return tree[k];
    ll mid = (l + r) >> 1;
    if(y <= mid) return ask(k << 1, x, y, l, mid);
    if(x >= mid + 1) return ask(k << 1 | 1, x, y, mid + 1, r);
    Tree a, b, c;
    a = ask(k << 1, x, y, l, mid);
    b = ask(k << 1 | 1, x, y, mid + 1, r);
    c = add(a, b);
    return c;
}
inline void change(ll k, ll x, ll l, ll r, ll d){
    if(l == r){
        tree[k].sum = d;
        tree[k].l = d;
        tree[k].r = d;
        tree[k].maxx = d;
        return ;
    }
    ll mid = (l + r) >> 1;
    if(x <= mid) change(k << 1, x, l, mid, d);
    if(mid + 1 <= x) change(k << 1| 1, x, mid + 1, r, d);
    tree[k] = add(tree[k << 1], tree[k << 1 | 1]);
}
int main(){
    n = read(), m = read();
    for(int i = 1;i <= n;i ++) a[i] = read();
    build(1, 1, n);
    while(m --){
        ll K, A, B;
        K = read(), A = read(), B = read();
        if(K == 2) change(1, A, 1, n, B);
        else
        {
            if(A > B) swap(A, B);
            Tree temp = ask(1, A, B, 1, n);
            printf("%lld\n", temp.maxx);
        }
    }
    return 0;
}