#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;
}