include<iostream>

include<fstream>

using namespace std;
const int N = 1LL<<19;
pair<int,int> arr[N];
long long n;
void update(int k, int x)
{
k+=n;
arr[k]={x,x};
k/=2;
while(k>=1)
{
arr[k].second = arr[2k].second + arr[2k+1].second;
arr[k].first = max(arr[2k].first, arr[2k].second + arr[2*k+1].first);
k/=2;
}
}
long long truyvan(int a, int b){
a+=n;
b+=n;
pair<int, int> x = {0, 0}, y = {0, 0};
while(a<=b){
if (a%2==1)
x = {max(x.first, x.second + arr[a].first), x.second + arr[a++].second};
if (b%2==0)
y = {max(arr[b].first, arr[b].second + y.second), y.second + arr[b--].second};
a/=2;
b/=2;
}
return max(x.first, x.second + y.first);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

long long t;
cin>>n>>t;
for (long long i = 0; i < n; i++)
{
    long long x; cin>>x;
    update(i, x);
}
while(t--)
{
    long long x, a, b;
    cin>>x>>a>>b;
    if (x == 1)
        update(a-1, b);
    else
        cout<<truyvan(a-1, b-1)<<endl;
}

}