《算法竞赛进阶指南》0x43线段树 单点修改+查询区间最大子段和

题目链接：https://www.acwing.com/problem/content/246/

线段树合并线段的时候要更新结点中的ans值，但是这个值的更新依赖于lmax与rmax，这两个值的更新又依赖于sum，故查询的时候需要返回的是一个结点，返回代表的区间的信息。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 500010;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
    int l,r,s,lx,rx,ans;
}t[maxn*4];
void pushup(int rt){
    t[rt].lx=max(t[rt<<1].lx,t[rt<<1].s+t[rt<<1|1].lx);
    t[rt].rx=max(t[rt<<1|1].rx,t[rt<<1|1].s+t[rt<<1].rx);
    t[rt].s=t[rt<<1].s+t[rt<<1|1].s;
    t[rt].ans=max(max(t[rt<<1].ans,t[rt<<1|1].ans),t[rt<<1].rx+t[rt<<1|1].lx);
}
void build(int rt,int l,int r){
    t[rt].l=l;
    t[rt].r=r;
    if(l==r){
        scanf("%d",&t[rt].ans);
        t[rt].lx=t[rt].rx=t[rt].s=t[rt].ans;
        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 pos,int C){
    if(t[rt].l==t[rt].r){
        t[rt].s=t[rt].lx=t[rt].rx=t[rt].ans=C;
        return;
    }
    int mid=(t[rt].l+t[rt].r)>>1;
    if(pos<=mid) update(rt<<1,pos,C);
    else update(rt<<1|1,pos,C);
    pushup(rt);
}
node query(int rt,int L,int R){
    if(t[rt].l>=L && t[rt].r<=R){
        return t[rt];
    }
    node ans1,ans2;
    int mid=(t[rt].l+t[rt].r)>>1;
    if(L<=mid && R>mid){
        ans1=query(rt<<1,L,R);
        ans2=query(rt<<1|1,L,R);
        node ans;
        ans.s=ans1.s+ans2.s;
        ans.lx=max(ans1.lx,ans1.s+ans2.lx);
        ans.rx=max(ans2.rx,ans2.s+ans1.rx);
        ans.ans=max(max(ans1.ans,ans2.ans),ans1.rx+ans2.lx);
        return ans;
    }else if(L>mid){
        return query(rt<<1|1,L,R);
    }else if(R<=mid){
        return query(rt<<1,L,R);
    }
}
int main(){
    cin>>n>>m;
    build(1,1,n);
    while(m--){
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if(t==1){
            if(x>y)swap(x,y);
            printf("%d
",query(1,x,y).ans);
        }else if(t==2){
            update(1,x,y);
        }
    }
    return 0;
}