#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
	struct Node {
		int sum, prefix_max, suffix_max, max_subarray_sum;
	};
	
	vector<Node> tree;
	int n;
	
	SegmentTree(int size) : n(size) {
		tree.resize(4 * size);
	}
	
	Node merge(const Node &left, const Node &right) {
		Node result;
		result.sum = left.sum + right.sum;
		result.prefix_max = max(left.prefix_max, left.sum + right.prefix_max);
		result.suffix_max = max(right.suffix_max, right.sum + left.suffix_max);
		result.max_subarray_sum = max({left.max_subarray_sum, right.max_subarray_sum, left.suffix_max + right.prefix_max});
		return result;
	}
	
	void build(const vector<int> &arr, int node, int start, int end) {
		if (start == end) {
			tree[node] = {arr[start], max(arr[start], 0), max(arr[start], 0), max(arr[start], 0)};
		} else {
			int mid = (start + end) >> 1;
			build(arr, node << 1, start, mid);
			build(arr, node << 1 | 1, mid + 1, end);
			tree[node] = merge(tree[node << 1], tree[node << 1 | 1]);
		}
	}
	
	Node query(int node, int start, int end, int l, int r) {
		if (r < start || end < l) {
			return {0, 0, 0, 0};
		}
		if (l <= start && end <= r) {
			return tree[node];
		}
		int mid = (start + end) >> 1;
		Node left_query = query(node << 1, start, mid, l, r);
		Node right_query = query(node << 1 | 1, mid + 1, end, l, r);
		return merge(left_query, right_query);
	}
	
	void update(int node, int start, int end, int idx, int value) {
		if (start == end) {
			tree[node] = {value, max(value, 0), max(value, 0), max(value, 0)};
		} else {
			int mid = (start + end) >> 1;
			if (idx <= mid) {
				update(node << 1, start, mid, idx, value);
			} else {
				update(node << 1 | 1, mid + 1, end, idx, value);
			}
			tree[node] = merge(tree[node << 1], tree[node << 1 | 1]);
		}
	}
};

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<int> arr(n);
	
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	SegmentTree segTree(n);
	segTree.build(arr, 1, 0, n - 1);
	
	while (m--) {
		int k, a, b;
		cin >> k >> a >> b;
		if (k == 1) {
			if (a > b) swap(a, b);
			cout << segTree.query(1, 0, n - 1, a - 1, b - 1).max_subarray_sum << '\n';
		} else if (k == 2) {
			segTree.update(1, 0, n - 1, a - 1, b);
		}
	}
	
	return 0;
}