#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 200005;
const int INF = 2e9;
int n, q, a[maxn];

struct node {
    ll sum, pref_sum;
};

node make_node(ll value) {
    node C;
    C.sum = value;
    C.pref_sum = max(0LL, value);
    
    return C;
}
node merge_nodes(node A, node B) {
    node C;
    C.sum = A.sum + B.sum;
    C.pref_sum = max(A.pref_sum, A.sum + B.pref_sum);
    
    return C;
}

node segment_tree[3 * maxn];

void build_tree(int L, int R, int node) {
    if(L == R) {
        segment_tree[node] = make_node(a[L]);
    }
    else {
        int middle = (L + R) / 2;
        build_tree(L, middle, 2 * node);
        build_tree(middle + 1, R, 2 * node + 1);
        segment_tree[node] = merge_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
    }
}

// L R i L R j L R
node query(int i, int j, int L, int R, int node) {
    if(i <= L and R <= j) {
        return segment_tree[node];
    }
    if(R < i or j < L) {
        return make_node(0);
    }
    
    int middle = (L + R) / 2;
    return merge_nodes(query(i, j, L, middle, 2 * node), query(i, j, middle + 1, R, 2 * node + 1));
}

void update(int idx, int new_value, int L, int R, int node) {
    if(L == R) {
        segment_tree[node] = make_node(new_value);
        return;
    }
    int middle = (L + R) / 2;
    if(idx <= middle) {
        update(idx, new_value, L, middle, 2 * node);
    }
    else {
        update(idx, new_value, middle + 1, R, 2 * node + 1);
    }
    
    segment_tree[node] = merge_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    build_tree(0, n - 1, 1);
    
    
    for(int i = 0; i < q; i++) {
        int t, x, y;
        cin >> t >> x >> y;
        
        if(t == 1) {
            update(x - 1, y, 0, n - 1, 1);
        }
        else {
            cout << query(x - 1, y - 1, 0, n - 1, 1).pref_sum << "\n";
        }
    }
    return 0;
}