怀着激动的心情,把大家都会的线段树学了一下.听说线段树博大精深,所以决定把进阶指南暂时放一放,学完这个把kuangbin的线段树专题也做了.emm.今天先更个不带lazy的线段树,虽然我觉得带不带lazy其实都差不多.但是,第一次写线段树,好激动哎...
首先介绍线段树的几个操作(不带lazy).
1.build

这个操作就是把已知信息转化为二叉搜索树,线段树就是一颗二叉搜索树,分治思想的体现.

2.pushup

这个操作就是通过子节点信息更新父节点.

3.modify

执行更新操作.

4.query

执行查询操作.

对于这个题目而言,线段树需要维护些什么信息呢?我们思考两段合并的最大连续子段和,就是能否从两个子区间->父区间.显然需要维护四个变量.然后加上区间的变量,一共就是6个变量,分别是:

int l,r;//当前节点左右区间范围.
int sum;//表示当前节点左右区间的总和.
int lmax,rmax,tmax;//分别表示当前节点最大前缀和,最大后缀和以及最大子段和.

这些节点怎么维护呢,也就是我们的pushup操作怎么操作的呢?首先对于sum来说,假设我们现在要更新的节点是u.那么怎么更新呢?

void pushup(node &u,node &left,node &right)
{
    u.sum=left.sum+right.sum;
    u.lmax=max(left.lmax,left.sum+right.lmax);
    u.rmax=max(right.rmax,right.sum+left.rmax);
    u.tmax=max(max(left.tmax,right.tmax),left,rmax+right,lmax);
}
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

这是这个题的关键思路就是这了,其他就没了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
ll w[N];
struct node{
    ll l,r,sum,lmax,rmax,tmax;
}tr[N*4];

void pushup(node &u,node &left,node &right)
{
    u.sum=left.sum+right.sum;
    u.lmax=max(left.lmax,left.sum+right.lmax);
    u.rmax=max(right.rmax,right.sum+left.rmax);
    u.tmax=max(max(left.tmax,right.tmax),left.rmax+right.lmax);

}

void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l==r)//递归出口.
    {
        tr[u]={l,r,w[l],w[l],w[l],w[l]};
        return;
    }
    else
    {
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x)//说明到了要改的点.
    {
        tr[u]={x,x,v,v,v,v};
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid)  modify(u<<1,x,v);//左边
        else        modify(u<<1|1,x,v);//右边
        pushup(u);
    }
}

node query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)  return tr[u];
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(mid>=r)//左边
        {
            return query(u<<1,l,r);
        }
        else if(l>mid)//右边
        {
            return query(u<<1|1,l,r);
        }
        else
        {
            auto left=query(u<<1,l,r);
            auto right=query(u<<1|1,l,r);
            node res;
            pushup(res,left,right);
            return res;
        }
    }
}

int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%lld",&w[i]);
    build(1,1,n);
    while(m--)
    {
        ll a,b,c;
        scanf("%lld",&a);
        if(a==1)//查询
        {
            scanf("%lld%lld",&b,&c);
            if(b>c) swap(b,c);
            cout<<query(1,b,c).tmax<<endl;
        }
        else//修改
        {
            scanf("%lld%lld",&b,&c);
            modify(1,b,c);//把b改成c
        }
    }
    return 0;
}