（分析见正睿2018.10.1笔记）
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
struct node {
int pre,sur,ans,sum;
};
node d[200100];
inline node work(node x,node y){
node res;
res.sum=x.sum+y.sum;
res.pre=max(x.pre,x.sum+y.pre);
res.sur=max(y.sur,y.sum+x.sur);
res.ans=max(max(x.ans,y.ans),x.sur+y.pre);
return res;
}
inline void update(int le,int ri,int wh,int pl,int k){
if(le==ri){
d[wh].pre=d[wh].sur=d[wh].ans=d[wh].sum=k;
return;
}
int mid=(le+ri)>>1;
if(mid>=pl)update(le,mid,wh<<1,pl,k);
else update(mid+1,ri,wh<<1|1,pl,k);
d[wh]=work(d[wh<<1],d[wh<<1|1]);
return;
}
inline node q(int le,int ri,int wh,int x,int y){
if(le>=x&&ri<=y){
return d[wh];
}
int mid=(le+ri)>>1,cnt=0;
node a,b;
if(mid>=x)cnt+=1,a=q(le,mid,wh<<1,x,y);
if(mid<y)cnt+=2,b=q(mid+1,ri,wh<<1|1,x,y);
if(cnt==1)return a;
if(cnt==2)return b;
return work(a,b);
}
int main(){
int n,m,i,j,k,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);
update(1,n,1,i,x);
}
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d%d%d",&k,&x,&y);
if(k==0){
update(1,n,1,x,y);
}else {
printf("%d
",q(1,n,1,x,y).ans);
}
}
return 0;
}