SP1716 GSS3 - Can you answer these queries III（线段树）

题意：

n 个数，q 次操作

操作0 x y把A_x修改为yy

操作1 l r询问区间[l, r] 的最大子段和

题解：

用线段树维护区间合并问题

每个结点维护4个信息：左边连续子段和，右边连续子段和，区间总和，最大子段和

1.区间总和很容易求。
2.左边连续子段和：由左儿子的左连续子段和 或者 左儿子的区间和 + 右儿子的左连续子段和
3.右边连续子段和：同理由右儿子的又连续子段和 或者 右儿子的区间和 + 左儿子的右连续子段和
4.最大子段和：假如最大子段和没经过中间，那么最大子段和就为左右儿子的最大子段和；假如经过了中间，那么最大子段和就为左儿子的右连续子段和+右儿子的左连续子段和

然后就和普通的线段树一样了

---

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
const int MOD = 998244353;
int n,Q,a[MAXN];
struct node{ int suml,sumr,sum,mx; }t[MAXN<<2];
inline void pushup(int rt){
    t[rt].suml = max(t[rt<<1].suml,t[rt<<1].sum+t[rt<<1|1].suml);
    t[rt].sumr = max(t[rt<<1|1].sumr,t[rt<<1|1].sum+t[rt<<1].sumr);
    t[rt].sum = t[rt<<1].sum + t[rt<<1|1].sum;
    t[rt].mx = max(max(t[rt<<1].mx,t[rt<<1|1].mx),t[rt<<1].sumr+t[rt<<1|1].suml);
}
void build(int rt,int l,int r){
    if(l==r) { t[rt].suml=t[rt].sumr=t[rt].sum=t[rt].mx=a[l]; return; }
    int mid=l+r>>1;
    build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void update(int rt,int l,int r,int x,int y){
    if(l==r) { t[rt].mx=t[rt].suml=t[rt].sumr=t[rt].sum=y; return; }
    int mid=l+r>>1;
    if(x<=mid) update(rt<<1,l,mid,x,y);
    else update(rt<<1|1,mid+1,r,x,y);
    pushup(rt);
}
node Query(int ql,int qr,int rt,int l,int r){
    if(ql<=l && r<=qr) return t[rt];
    int mid=l+r>>1;
    if(qr<=mid) return Query(ql,qr,rt<<1,l,mid);
    else if(ql>mid) return Query(ql,qr,rt<<1|1,mid+1,r);
    else{
        node L=Query(ql,mid,rt<<1,l,mid),R=Query(mid+1,qr,rt<<1|1,mid+1,r);
        node ans;
        ans.sum=L.sum+R.sum;
        ans.suml=max(L.suml,L.sum+R.suml);
        ans.sumr=max(R.sumr,R.sum+L.sumr);
        ans.mx = max(max(L.mx,R.mx),L.sumr+R.suml);
        return ans;
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    scanf("%d",&Q);
    while(Q--){
        int op,x,y; scanf("%d%d%d",&op,&x,&y);
        if(op==1) printf("%d\n",Query(x,y,1,1,n).mx);
        else update(1,1,n,x,y);
    }
    return 0;
}