题目链接
很经典的在线求区间子段和问题，
求子段和我们需要维护四个信息：
\(sum[p]\) : 区间和
\(lmx[p]\) : 节点\(p\)靠左的最大子段和
\(rmx[p]\) : 节点\(p\)靠右的最大子段和
\(dat[p]\) : 节点\(p\)的最大子段和
所以显而易见:
在\(query\)的时候，用\(ans\)统计最大子段和，
另外还要开一个\(pr\)计算之前搞好的靠右的子段和，
最后取\(max\)即可，
Code:
#define ll long long
#define inf (1<<30)
using namespace std;
const int N=4e5+10;
int n,T,a[N],ans,pr;
int lmx[N],rmx[N],sum[N],dat[N];
void updata(int p){
sum[p]=sum[p<<1]+sum[p<<1|1];
lmx[p]=max(lmx[p<<1],sum[p<<1]+lmx[p<<1|1]);
rmx[p]=max(rmx[p<<1|1],sum[p<<1|1]+rmx[p<<1]);
dat[p]=max(max(dat[p<<1],dat[p<<1|1]),rmx[p<<1]+lmx[p<<1|1]);
}
void build(int p,int l,int r){
if(l==r){
lmx[p]=rmx[p]=dat[p]=sum[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
updata(p);return;
}
void change(int p,int l,int r,int x,int v){
if(l==r){
a[x]=v;
lmx[p]=rmx[p]=dat[p]=sum[p]=v;
return;
}
int mid=(l+r)>>1;
if(x<=mid)change(p<<1,l,mid,x,v);
else change(p<<1|1,mid+1,r,x,v);
updata(p);return;
}
void ask(int p,int l,int r,int x,int y){
if(x<=l&&y>=r){
ans=max(ans,max(dat[p],pr+lmx[p]));
pr=max(pr+sum[p],rmx[p]);
return;
}
int mid=(l+r)>>1;
if(x<=mid)ask(p<<1,l,mid,x,y);
if(y>mid)ask(p<<1|1,mid+1,r,x,y);
}
void clear(){ans=-inf,pr=-inf;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&T);
int op,l,r;
while(T--){
scanf("%d%d%d",&op,&l,&r);
if(op==1){
clear();
ask(1,1,n,l,r);
printf("%d\n",ans);
}
else change(1,1,n,l,r);
}
return 0;
}