其實把update看懂就很好說了，沒什麼特別難理解的
luogu_P4513小白逛公園
#include<iostream> #include<cstdio> #define ll long long #define ls p<<1 #define rs p<<1|1 using namespace std; const int maxn=500005; int n,m; struct node{ ll sum,mx,l,r;//包含左/右端点最大子段和 }t[maxn<<2]; ll a[maxn]; inline int max(int a,int b){return a<b?b:a;} void upd(int p){ t[p].l=max(t[ls].l,t[ls].sum+t[rs].l); //选包含左边端点那段 或者把左半边全选上加上右半边包含左端点 t[p].r=max(t[rs].r,t[rs].sum+t[ls].r); t[p].mx=max( max(t[ls].mx,t[rs].mx),t[ls].r+t[rs].l); //这段的最大子段和 t[p].sum=t[ls].sum+t[rs].sum; } void build(int p,int l,int r) { if(l==r){ t[p].sum=t[p].mx=t[p].l=t[p].r=a[l];return; } int mid=(l+r)/2; build(ls,l,mid);build(rs,mid+1,r); upd(p); } void change(int p,int l,int r,int pos,ll k) { if(l==r){ t[p].mx=t[p].l=t[p].r=t[p].sum=k;return; } int mid=(l+r)/2; if(pos>mid)change(rs,mid+1,r,pos,k); else change(ls,l,mid,pos,k); upd(p); } node query(int p,int l,int r,int LL,int RR)//因为最大值不是直接取就行，所以传一个node { if(l==LL && r==RR)return t[p]; int mid=(l+r)/2; if(RR<=mid)return query(ls,l,mid,LL,RR); else if(LL>mid)return query(rs,mid+1,r,LL,RR); node x=query(ls,l,mid,LL,mid),y=query(rs,mid+1,r,mid+1,RR),ret; //和update道理一样 ret.l=max(x.l,x.sum+y.l); ret.r=max(y.r,y.sum+x.r); ret.mx=max( max(x.mx,y.mx),x.r+y.l ); ret.sum=x.sum+y.sum; return ret; } int main() { scanf("%d%d",&n,&m); // memset(t,0xcf,sizeof(t)); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); while(m--){ int l,r;ll k; scanf("%lld%d%d",&k,&l,&r); if(k==1){ if(l>r)swap(l,r); printf("%lld ",query(1,1,n,l,r).mx); } else change(1,1,n,l,r); } }