#include<bits/stdc++.h>
using namespace std;
#define int long long
#define input(a,start,end) for(int i=start;i<end;i++){cin>>a[i];}
#define output(a,start,end) for(int i=start;i<end;i++){cout<<a[i]<<" ";}
int lazy[2000001];
void build(int ind, int low, int high, vector<int>&psum, vector<int>&seg){
if(low==high){
seg[ind] = psum[low];
return;
}
int mid = low+(high-low)/2;
build(2*ind+1, low, mid, psum, seg);
build(2*ind+2, mid+1, high, psum, seg);
seg[ind] = max(seg[2*ind+1], seg[2*ind+2]);
return;
}
void lazy_prop(vector<int>&seg,int ind,int low,int high){
seg[ind]+=lazy[ind];
lazy[2*ind+1]+=lazy[ind];
lazy[2*ind+2]+=lazy[ind];
lazy[ind] = 0;
}
int range_query(int ind, int low, int high, int l, int r, vector<int>&seg){
lazy_prop(seg,ind,low,high);
//no overlap
if(high<l || r<low){
return LLONG_MIN;
}
//complete overlap
if(low>=l && high<=r){
return seg[ind];
}
int mid = low+(high-low)/2;
int l_part = range_query(2*ind+1, low, mid, l, r, seg);
int r_part = range_query(2*ind+2, mid+1, high, l, r, seg);
return max(l_part, r_part);
}
void range_update(int l,int r, int u, int ind, int low, int high, vector<int>&seg){
//no overlap
if(high<l || r<low){
return;
}
//complete overlap
if(low>=l && high<=r){
lazy[ind]+=u;
lazy_prop(seg,ind,low,high);
return;
}
int mid = low+(high-low)/2;
range_update(l,r,u,2*ind+1,low,mid,seg);
range_update(l,r,u,2*ind+2,mid+1,high,seg);
seg[ind] = max(seg[2*ind+1], seg[2*ind+2]);
return;
}
int point_query(int ind,int low,int high,int k,vector<int>&seg){
lazy_prop(seg,ind,low,high);
if(low==high) return seg[ind];
int mid = low+(high-low)/2;
if(k<=mid) return point_query(2*ind+1,low,mid,k,seg);
return point_query(2*ind+2,mid+1,high,k,seg);
}
void solve(){
int n,q; cin>>n>>q;
vector<int>a(n);
memset(lazy,0,sizeof(lazy));
input(a,0,n);
vector<int>seg(4*n+1);
vector<int>psum(n);
psum[0] = a[0];
for(int i=1;i<n;i++) psum[i] = psum[i-1]+a[i];
build(0,0,n-1,psum,seg);
for(int i=0;i<q;i++){
int type; cin>>type;
if(type==1){
int k,val; cin>>k>>val;
range_update(k-1,n-1,val-a[k-1],0,0,n-1,seg);
a[k-1] = val;
}
else{
int l,r; cin>>l>>r;
int offset = l>=2?point_query(0,0,n-1,l-2,seg):0;
cout<<max((int)0,range_query(0,0,n-1,l-1,r-1,seg)-offset)<<endl;
}
}
}
signed main(){
solve();
cout<<endl;
}
//some thing is wrong in this sol... first two test cases are failing
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgaW5wdXQoYSxzdGFydCxlbmQpIGZvcihpbnQgaT1zdGFydDtpPGVuZDtpKyspe2Npbj4+YVtpXTt9CiNkZWZpbmUgb3V0cHV0KGEsc3RhcnQsZW5kKSBmb3IoaW50IGk9c3RhcnQ7aTxlbmQ7aSsrKXtjb3V0PDxhW2ldPDwiICI7fQoKaW50IGxhenlbMjAwMDAwMV07CnZvaWQgYnVpbGQoaW50IGluZCwgaW50IGxvdywgaW50IGhpZ2gsIHZlY3RvcjxpbnQ+JnBzdW0sIHZlY3RvcjxpbnQ+JnNlZyl7CiAgICBpZihsb3c9PWhpZ2gpewogICAgICAgIHNlZ1tpbmRdID0gcHN1bVtsb3ddOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQgPSBsb3crKGhpZ2gtbG93KS8yOwogICAgYnVpbGQoMippbmQrMSwgbG93LCBtaWQsIHBzdW0sIHNlZyk7CiAgICBidWlsZCgyKmluZCsyLCBtaWQrMSwgaGlnaCwgcHN1bSwgc2VnKTsKICAgIHNlZ1tpbmRdID0gbWF4KHNlZ1syKmluZCsxXSwgc2VnWzIqaW5kKzJdKTsKICAgIHJldHVybjsKfQoKdm9pZCBsYXp5X3Byb3AodmVjdG9yPGludD4mc2VnLGludCBpbmQsaW50IGxvdyxpbnQgaGlnaCl7CiAgICBzZWdbaW5kXSs9bGF6eVtpbmRdOyAKICAgIGxhenlbMippbmQrMV0rPWxhenlbaW5kXTsKICAgIGxhenlbMippbmQrMl0rPWxhenlbaW5kXTsKICAgIGxhenlbaW5kXSA9IDA7Cn0KaW50IHJhbmdlX3F1ZXJ5KGludCBpbmQsIGludCBsb3csIGludCBoaWdoLCBpbnQgbCwgaW50IHIsIHZlY3RvcjxpbnQ+JnNlZyl7CiAgICBsYXp5X3Byb3Aoc2VnLGluZCxsb3csaGlnaCk7CiAgICAvL25vIG92ZXJsYXAKICAgIGlmKGhpZ2g8bCB8fCByPGxvdyl7CiAgICAgICAgcmV0dXJuIExMT05HX01JTjsKICAgIH0KICAgIC8vY29tcGxldGUgb3ZlcmxhcAogICAgaWYobG93Pj1sICYmIGhpZ2g8PXIpewogICAgICAgIHJldHVybiBzZWdbaW5kXTsKICAgIH0KICAgIGludCBtaWQgPSBsb3crKGhpZ2gtbG93KS8yOwogICAgaW50IGxfcGFydCA9IHJhbmdlX3F1ZXJ5KDIqaW5kKzEsIGxvdywgbWlkLCBsLCByLCBzZWcpOyAKICAgIGludCByX3BhcnQgPSByYW5nZV9xdWVyeSgyKmluZCsyLCBtaWQrMSwgaGlnaCwgbCwgciwgc2VnKTsKICAgIHJldHVybiBtYXgobF9wYXJ0LCByX3BhcnQpOwp9CnZvaWQgcmFuZ2VfdXBkYXRlKGludCBsLGludCByLCBpbnQgdSwgaW50IGluZCwgaW50IGxvdywgaW50IGhpZ2gsIHZlY3RvcjxpbnQ+JnNlZyl7CiAgICAvL25vIG92ZXJsYXAKICAgIGlmKGhpZ2g8bCB8fCByPGxvdyl7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgLy9jb21wbGV0ZSBvdmVybGFwCiAgICBpZihsb3c+PWwgJiYgaGlnaDw9cil7CiAgICAgICAgbGF6eVtpbmRdKz11OwogICAgICAgIGxhenlfcHJvcChzZWcsaW5kLGxvdyxoaWdoKTsgCiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IG1pZCA9IGxvdysoaGlnaC1sb3cpLzI7CiAgICByYW5nZV91cGRhdGUobCxyLHUsMippbmQrMSxsb3csbWlkLHNlZyk7CiAgICByYW5nZV91cGRhdGUobCxyLHUsMippbmQrMixtaWQrMSxoaWdoLHNlZyk7CiAgICBzZWdbaW5kXSA9IG1heChzZWdbMippbmQrMV0sIHNlZ1syKmluZCsyXSk7CiAgICByZXR1cm47Cn0KaW50IHBvaW50X3F1ZXJ5KGludCBpbmQsaW50IGxvdyxpbnQgaGlnaCxpbnQgayx2ZWN0b3I8aW50PiZzZWcpewogICAgbGF6eV9wcm9wKHNlZyxpbmQsbG93LGhpZ2gpOwogICAgaWYobG93PT1oaWdoKSByZXR1cm4gc2VnW2luZF07CiAgICBpbnQgbWlkID0gbG93KyhoaWdoLWxvdykvMjsKICAgIGlmKGs8PW1pZCkgcmV0dXJuIHBvaW50X3F1ZXJ5KDIqaW5kKzEsbG93LG1pZCxrLHNlZyk7CiAgICByZXR1cm4gcG9pbnRfcXVlcnkoMippbmQrMixtaWQrMSxoaWdoLGssc2VnKTsKfQp2b2lkIHNvbHZlKCl7CiAgICBpbnQgbixxOyBjaW4+Pm4+PnE7CiAgICB2ZWN0b3I8aW50PmEobik7CiAgICBtZW1zZXQobGF6eSwwLHNpemVvZihsYXp5KSk7CiAgICBpbnB1dChhLDAsbik7CiAgICB2ZWN0b3I8aW50PnNlZyg0Km4rMSk7CiAgICB2ZWN0b3I8aW50PnBzdW0obik7CiAgICBwc3VtWzBdID0gYVswXTsKICAgIGZvcihpbnQgaT0xO2k8bjtpKyspIHBzdW1baV0gPSBwc3VtW2ktMV0rYVtpXTsKICAgIGJ1aWxkKDAsMCxuLTEscHN1bSxzZWcpOwogICAgZm9yKGludCBpPTA7aTxxO2krKyl7CiAgICAgICAgaW50IHR5cGU7IGNpbj4+dHlwZTsKICAgICAgICBpZih0eXBlPT0xKXsKICAgICAgICAgICAgaW50IGssdmFsOyBjaW4+Pms+PnZhbDsKICAgICAgICAgICAgcmFuZ2VfdXBkYXRlKGstMSxuLTEsdmFsLWFbay0xXSwwLDAsbi0xLHNlZyk7CiAgICAgICAgICAgIGFbay0xXSA9IHZhbDsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgaW50IGwscjsgY2luPj5sPj5yOwogICAgICAgICAgICBpbnQgb2Zmc2V0ID0gbD49Mj9wb2ludF9xdWVyeSgwLDAsbi0xLGwtMixzZWcpOjA7CiAgICAgICAgICAgIGNvdXQ8PG1heCgoaW50KTAscmFuZ2VfcXVlcnkoMCwwLG4tMSxsLTEsci0xLHNlZyktb2Zmc2V0KTw8ZW5kbDsKICAgICAgICB9CiAgICB9CiAgICAKfQpzaWduZWQgbWFpbigpewogICAgc29sdmUoKTsKICAgIGNvdXQ8PGVuZGw7Cn0KLy9zb21lIHRoaW5nIGlzIHdyb25nIGluIHRoaXMgc29sLi4uIGZpcnN0IHR3byB0ZXN0IGNhc2VzIGFyZSBmYWlsaW5n