本文共 2392 字，大约阅读时间需要 7 分钟。

题意：

求一个区间的最大连续和。 0：表示把A[x]改成y 1：表示求[x,y]这个区间的最大连续和。

题解：

线段树维护四个变量。 倒着讲，先来看如何维护这四个变量。 summax代表这个区间连续最大值，sum代表这个区间总和，lmax代表区间左端开始最大连序值，rmax代表区间右端开始最大连续值。

1.summax：

题目要求要连续，所以summax由他下面两端区间计算得出： $summax[node]=max(max(summax[ls],summax[rs]),lmax[rs]+rmax[ls]);$ 也就是 左孩子的区间最大、有孩子的区间最大、（左孩子的rmax+有孩子的lmax）这三个值得最大组成。 2.sum不必多说，线段树模板。 3.lmax： $lmax[node]=max(lmax[ls],sum[ls]+lmax[rs]);$ 可能有两种方法： (1).左孩子的lmax (2).左孩子全部+有孩子的lmax （也是node结点的lmax） 这两者取最大 4.rmax同理： $rmax[node]=max(rmax[rs],sum[rs]+rmax[ls]);$ 图略。

对于query时，上面的所说的维护同时适用，同时返回四个参数计算，我们可以选择引用的方法进行传递。

代码：

/*Keep on going Never give up*///#pragma GCC optimize(3,"Ofast","inline")#include
   
    //#include
    
     //#include
     
      //#include
      
       //#include
       
        //#include
        
         #define int long long#define ls 2*node#define rs 2*node+1#define endl '\n'using namespace std;const int maxn=4e5+10;const int mod=1e9+7;int a[maxn];int sum[maxn],lmax[maxn],rmax[maxn],summax[maxn];void pushup(int node){ summax[node]=max(max(summax[ls],summax[rs]),lmax[rs]+rmax[ls]); lmax[node]=max(lmax[ls],sum[ls]+lmax[rs]); rmax[node]=max(rmax[rs],sum[rs]+rmax[ls]); sum[node]=sum[ls]+sum[rs];}void build(int node,int start,int ends){ if(start==ends){ summax[node]=sum[node]=lmax[node]=rmax[node]=a[start]; return ; } int mid=(start+ends)/2; build(ls,start,mid); build(rs,mid+1,ends); pushup(node);}void query(int node,int start,int ends,int l,int r,int &Smax,int &Lmax,int &Rmax,int &Sum){ if(l<=start&&ends<=r){ Smax=summax[node]; Lmax=lmax[node]; Rmax=rmax[node]; Sum=sum[node]; return ; } int mid=(start+ends)/2; int smaxl=-1e9,lmaxl=-1e9,rmaxl=-1e9,suml=0; int smaxr=-1e9,lmaxr=-1e9,rmaxr=-1e9,sumr=0; if(l<=mid) query(ls,start,mid,l,r,smaxl,lmaxl,rmaxl,suml); if(mid
         
          >n; for(int i=1;i<=n;i++) cin>>a[i]; int q; cin>>q; build(1,1,n); while(q--){ int l,r; int opt; cin>>opt; if(!opt){ cin>>l>>r; update(1,1,n,l,r); } else{ cin>>l>>r; int ans,xx,yy,zz; query(1,1,n,l,r,ans,xx,yy,zz); cout<
          
           <