题目描述

单点修改,区间查询,求最大子段和

样例

input

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

output

2
-1

线段树

算法

lans,该区间内前缀和最大值
rans,后缀和最大值
ans,最大子段和
sum，区间和

update：
lans：左儿子lans 或 左儿子sum+右儿子lans
rans同理
ans是 左儿子ans 或 右儿子ans 或左儿子rans+右儿子lans
sum直接左右儿子相加

query：
1.查询区间包含在当前区间内：直接返回t[rt]
2.查询区间与右子树区间无重合：去左子树算答案
3.查询区间与左子树区间无重合 去右子树
4.其他直接像update中一般更新

备注：
这位dalao的解释也许更加清楚

时间复杂度O(mlogn)

每次操作logn（应该是吧）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,m,a[N];
struct pos{
    int l,r,ans,lans,rans,sum;
}t[N<<2];
void build(int rt,int l,int r){
//  cout<<"ee"<<rt<<" "<<l<<" "<<r<<endl;
    t[rt].l=l;t[rt].r=r;
    if(l==r){
        t[rt].lans=t[rt].rans=t[rt].ans=t[rt].sum=a[l];
        return;
    }

    int mid=(l+r)>>1; 
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);

    t[rt].ans=max(t[rt<<1].rans+t[rt<<1|1].lans,max(t[rt<<1].ans,t[rt<<1|1].ans));
    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    t[rt].lans=max(t[rt<<1].lans,t[rt<<1].sum+t[rt<<1|1].lans);
    t[rt].rans=max(t[rt<<1|1].rans,t[rt<<1].rans+t[rt<<1|1].sum);
    return;
}
void update(int rt,int x,int v){
    if(t[rt].l==t[rt].r){
        t[rt].lans=t[rt].rans=t[rt].ans=t[rt].sum=v;
        return;
    }

    int mid=(t[rt].l+t[rt].r)>>1; 
    if(x<=mid) update(rt<<1,x,v);
    else update(rt<<1|1,x,v);

    t[rt].ans=max(t[rt<<1].rans+t[rt<<1|1].lans,max(t[rt<<1].ans,t[rt<<1|1].ans));
    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    t[rt].lans=max(t[rt<<1].lans,t[rt<<1].sum+t[rt<<1|1].lans);
    t[rt].rans=max(t[rt<<1|1].rans,t[rt<<1].rans+t[rt<<1|1].sum);
}
pos query(int rt,int L,int R){
    pos qaq,tmpl,tmpr;
    if(L<=t[rt].l&&t[rt].r<=R){
    //  cout<<"ee:"<<t[rt].ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
        return t[rt];
    }

    int mid=(t[rt].l+t[rt].r)>>1;
    if(R<=mid){
    //  cout<<"ee:"<<query(rt<<1,L,R).ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
        return query(rt<<1,L,R);
    }
    if(mid<L){
    //  cout<<"ee:"<<query(rt<<1|1,L,R).ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
        return query(rt<<1|1,L,R);
    }

    //L<t[rt].l<R<t[rt].r
    tmpl=query(rt<<1,L,R);tmpr=query(rt<<1|1,L,R);
    qaq.ans=max(tmpl.rans+tmpr.lans,max(tmpl.ans,tmpr.ans));
    qaq.lans=max(tmpl.lans,tmpl.sum+tmpr.lans);
    qaq.rans=max(tmpr.rans,tmpr.sum+tmpl.rans);
    qaq.sum=tmpl.sum+tmpr.sum;
//  cout<<"ee:"<<qaq.ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
    return qaq;
}
int main(){
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1){
            if(x>y) swap(x,y);
            printf("%d\n",query(1,x,y).ans);
        } else update(1,x,y);
    } 
    return 0;
}