线段树【p1115】 最大子段和
2024-08-29 19:03:25
题目描述-->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(x<=l 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));
}
最新文章
- 项目 CTR预估
- 使用NPOI将数据导出为word格式里的table
- 如何测试手机上的SOAP客户端
- Struts2 Action与Servlet API耦合
- iOS移动开发周报-第23期
- 防止 SQL 注入的方法（摘抄）
- 封装insertAfter、addClass、格式化时间
- android 小知识点
- 巧谈 GCD
- listener笔记
- iOS-设计模式之代理反向传值
- FTP上传下载工具(FlashFXP) v5.5.0 中文版
- 我了解到的JavaScript异步编程
- CSAPP：第二章学习笔记：斗之气2段
- python scrapy 爬取西刺代理ip(一基础篇)（ubuntu环境下） -赖大大
- javaScript系列 [05]-javaScript和JSON
- react native 淘宝镜像
- js判断某年某月有多少天
- Linux 下搭建流媒体服务器
- 深入理解Java虚拟机，intern