```cpp
#include<cstdio>
#include<iostream>
#define MAXN 500005
using namespace std;
struct node {
int l,r;
int sum,lx,rx,sumx;
} a[MAXN4];
int n,b[MAXN4],m,k,x,y;
void updata(int x) {
int l=x2,r=x2+1;
a[x].sum=a[l].sum+a[r].sum;
a[x].sumx=max(max(a[l].sumx,a[r].sumx),a[l].rx+a[r].lx);
a[x].rx=max(a[r].rx,a[l].rx+a[r].sum);
a[x].lx=max(a[l].lx,a[l].sum+a[r].lx);
}
void build(int x,int l,int r) {
a[x].l=l,a[x].r=r;
if(l==r) {
a[x].sum=a[x].sumx=a[x].lx=a[x].rx=b[l];
return ;
}
build(x2,l,(l+r)/2);
build(x2+1,(l+r)/2+1,r);
updata(x);
}
void change(int num,int x,int y) {
if(a[num].l==a[num].r) {
a[num].sum=a[num].sumx=a[num].lx=a[num].rx=y;
return;
}
int mid=(a[num].l+a[num].r)/2;
if(x<=mid)change(num2,x,y);
else change(num2+1,x,y);
updata(num);
}
node get(int num,int l,int r) {
if(a[num].l>=l&&a[num].r<=r) {
return a[num];
}
node g,gg;
int mid=(a[num].l+a[num].r)/2;
if(l>mid)return get(num2+1,l,r);
else if(r<=mid) return gg=get(num2,l,r);
else {
g=get(num2,l,r);
gg=get(num2+1,l,r);
node ans;
ans.sumx=max(max(g.sumx,gg.sumx),g.rx+gg.lx);
ans.lx=max(g.lx,g.sum+gg.lx);
ans.rx=max(gg.rx,g.sum+gg.rx);
return ans;
}
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&b[i]);
}
build(1,1,n);
scanf("%d",&m);
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&k,&x,&y);
if(k==0) {
change(1,x,y);
} else {
if(x>y)swap(x,y);
printf("%d\n",get(1,x,y).sumx);
}
}
return 0;
}
```
by Siyuan @ 2018-06-17 15:59:14