首页 > 其他 > 详细

p1115 最大子段和(线段树)

时间:2018-09-22 20:30:24      阅读:165      评论:0      收藏:0      [点我收藏+]

题目描述-->p1115 最大子段和

虽然是一个普及-的题,但我敲了线段树 qwq

数组定义

\(lsum[ ]\)代表 该区间左端点开始的最大连续和.

\(rsum[ ]\)代表 该区间右端点开始的最大连续和.

\(ssum[ ]\)代表 区间内最大连续和.

\(sum[ ]\) 代表区间和.

Que and A

Q:已知一个区间的左右区间的最大连续和,如何合并?

A:这个区间的最大连续和要么是左子区间的最大连续和,要么是右子区间的最大连续和.

 要么是左子区间的最大右起子段和+右子区间的最大左起字段和.

code\(ssum[o]=max(max(ssum[lson],ssum[rson]),rsum[lson]+lsum[rson])\)

Q:如何更新区间最大左起子段和.

A:新区间的最大左起子段和.要么是其左子区间最大连续和,要么是其左子区间和+右子区间的左起子段和.

最大右起子段和同理

code\(lsum[o]=max(lsum[lson],sum[lson]+lsum[rson])\)

     \(rsum[o]=max(rsum[rson],sum[rson]+rsum[lson])\)

更新操作类似单点修改

贴一下代码 qwq.

#include<bits/stdc++.h>
#define IL inline
#define int long long
#define RI register int
#define N 200008
#define ls o<<1
#define rs o<<1|1
using namespace std;
IL void in(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int tr[N<<2],ssum[N<<2],lsum[N<<2],rsum[N<<2],n;
IL void up(int o)
{
    tr[o]=tr[ls]+tr[rs];
    ssum[o]=max(max(ssum[ls],ssum[rs]),rsum[ls]+lsum[rs]);
    lsum[o]=max(lsum[ls],tr[ls]+lsum[rs]);
    rsum[o]=max(rsum[rs],tr[rs]+rsum[ls]);
}
IL void build(int o,int l,int r)
{
    if(l==r)
    {
        in(tr[o]);
        ssum[o]=lsum[o]=rsum[o]=tr[o];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(o);
}
IL int query(int o,int l,int r,int x,int y)
{
    if(l<=x and y>=r)return ssum[o];
    int mid=(l+r)>>1;
    int ret=-2147483647;
    if(x<=mid)ret=max(query(ls,l,mid,x,y),ret);
    if(y>mid)ret=max(query(rs,mid+1,r,x,y),ret);
    return ret;
}

main(void )
{
    in(n);
    build(1,1,n);
    printf("%lld",query(1,1,n,1,n));
}

p1115 最大子段和(线段树)

原文:https://www.cnblogs.com/-guz/p/9690947.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!