[基础例题] 线段树

背景：最近czy刚讲了segmenttree，整理例题。

线段树操作要考虑：

0.记录必要数值

1.支持区间合并

2.标记覆盖

3.标记下放（cpu监控），数值上推（楼房重建）

4.保证log

...........

T1：

$n 个数，$

操作0 x y把

操作1 l r询问区间

即：带修最长子段和。

分析：

显然，一个区间的最大子段和，假如我们像线段树操作一样，把它劈成两半，这个子段和，要么是从ls左端点开始的一段，要么是rs右端点开始一段，要么是ls右端点开始一段和rs左端点开始一段，或者是ls/rs最大子段和。

所以，线段树里记录sum,lmx,rmx,zui 分别是总和，左端点开始最大子段和，右端点开始的最大子段和，区间最大子段和。

难点在于query,其实本质就是根据已有区间的情况，重组一个新的区间情况。

czy们的做法是，传一个结构体，里面记录新拆分的区间的sum,lmx,rmx,zui。比较好的做法，体现了重组新区间的本质。

我的做法是：每次传入c，表示要处理出区间的左端点开始最大值、右端点开始最大值、或者最大子段和。

注意的是，如果要传入查询最大子段和(c=3),左端点开始(c=1)，或者右端点开始时，

对于区间分割的情况不同（L<=mid/mid<R），根据当前的c不同，传入的c也是不同的。

否则会出现的错误是：把查询区间拆成两半，结果可能取了两边儿子的各自最大子段和做和，但是可能这两个子区间并不是连续的。

详见代码：

#include<bits/stdc++.h>
using namespace std;
const int N=50000+10;
typedef long long ll;
const ll inf=2e18+1;
struct node{
    ll sum,lmx,rmx;
    ll zui;
}t[4*N];
int n,m;
ll a[N];
void pushup(int x)
{
    int ls=x<<1,rs=x<<1|1;
    t[x].sum=t[ls].sum+t[rs].sum;
    t[x].lmx=max(t[ls].sum+t[rs].lmx,t[ls].lmx);
    t[x].rmx=max(t[rs].sum+t[ls].rmx,t[rs].rmx);
    t[x].zui=max(t[rs].zui,max(t[ls].zui,t[ls].rmx+t[rs].lmx));
}
void build(int x,int l,int r)
{
    if(l==r){
        t[x].lmx=t[x].rmx=t[x].sum=a[l];
        t[x].zui=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void ch(int x,int l,int r,int to,ll val)
{
    if(l==r){
        t[x].sum=t[x].rmx=t[x].lmx=val;
        t[x].zui=val;
        return;
    }
    int mid=(l+r)>>1;
    if(to<=mid) ch(x<<1,l,mid,to,val);
    else ch(x<<1|1,mid+1,r,to,val);
    pushup(x);
}
ll query(int x,int l,int r,int L,int R,int c)
{
    if(L<=l&&r<=R){
        if(c==3)
        return t[x].zui;
        if(c==1)
        return t[x].lmx;
        if(c==2) 
        return t[x].rmx;
        if(c==4)
        return t[x].sum;
    }
    int mid=(l+r)>>1;
    ll ret=-inf;
    if(L<=mid&&mid<R){//注意这里的判断 
        if(c==3){
        ret=max(ret,query(x<<1,l,mid,L,R,3));
        ret=max(ret,query(x<<1|1,mid+1,r,L,R,3));
        ret=max(ret,query(x<<1,l,mid,L,R,2)+query(x<<1|1,mid+1,r,L,R,1));
        }
        else if(c==2){
            ret=max(ret,query(x<<1,l,mid,L,R,2)+t[x<<1|1].sum);
            ret=max(ret,query(x<<1|1,mid+1,r,L,R,2));
        }
        else{
            ret=max(ret,t[x<<1].sum+query(x<<1|1,mid+1,r,L,R,1));
            ret=max(ret,query(x<<1,l,mid,L,R,1));
        }
    }
    else if(L<=mid){ret=max(ret,query(x<<1,l,mid,L,R,c));}
    else if(mid<R){ret=max(ret,query(x<<1|1,mid+1,r,L,R,c));}
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    int op,l,r,go;
    ll v;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op){
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1,1,n,l,r,3));
        }
        else{
            scanf("%d%lld",&go,&v);
            ch(1,1,n,go,v);
        }
    }
    return 0;
}

T2：

题目大意：

给定长度为

[基础例题] 线段树

推荐阅读