注：本贴仅用于记录我自己对于线段树的区间最大子段和操作一些粗略理解，方便以后重新回忆
注：如果本帖对你有帮助，那并不是我的本意（笑
线段树的区间最大子段和操作大致可以分为两种：（但我不知道他们的名字分别叫什么）
第一种：
对于每个子段，我们维护这些东西：
记录区间和
记录包含最左端的最大字段和
记录包含最右端的最大字段和
记录最大字段和
那么如何维护这些区间呢？见代码：
push_up(int s){
int ls=s*2,rs=s*2+1;
t[s].sum=t[ls].sum+t[rs].sum;
t[s].l=max(t[ls].l,t[ls].sum+t[rs].l);
t[s].r=max(t[rs].r,t[rs].sum+t[ls].r);
t[s].mx=max(max(t[ls].mx,t[rs].mx),t[ls].r+t[s].l);
}
真是让人头大呢
查询也是类似操作哦~~
这一算法支持单点修改操作，每次修改完按照以上步骤 即可
刚好有一份不知道什么时候写的代码(这里的代码实现的是至少取一个数的区间最大子段和）：
数组代替
数组代替
数组代替
数组代替
using namespace std;
struct hh{
int l,r,m,sum;
};
int n,m,q,x,y;
int a[500010],t[2000010];
int ml[2000010],mr[2000010],mm[2000010];
void push_up(int s){
t[s]=t[s*2]+t[s*2+1];
ml[s]=max(ml[s*2],t[s*2]+ml[s*2+1]);
mr[s]=max(mr[s*2+1],t[s*2+1]+mr[s*2]);
mm[s]=max(mr[s*2]+ml[s*2+1],max(mm[s*2],mm[s*2+1]));
}
void build(int s,int l,int r){
if(l==r){
ml[s]=mr[s]=mm[s]=t[s]=a[l];
return ;
}
int mid=(l+r)/2;
build(s*2,l,mid);
build(s*2+1,mid+1,r);
push_up(s);
}
void add(int s,int l,int r,int x,int k){
if(l==r){
ml[s]=mr[s]=mm[s]=t[s]=k;
return ;
}
int mid=(l+r)/2;
if(x<=mid) add(s*2,l,mid,x,k);
else add(s*2+1,mid+1,r,x,k);
push_up(s);
}
hh sc(int s,int l,int r,int x,int y){
if(x<=l&&r<=y) return (hh){ml[s],mr[s],mm[s],t[s]};
int mid=(l+r)/2;
if(y<=mid) return sc(s*2,l,mid,x,y);
else if(x>mid) return sc(s*2+1,mid+1,r,x,y);
else{
hh ll=sc(s*2,l,mid,x,y);
hh rr=sc(s*2+1,mid+1,r,x,y);
int scl=max(ll.l,ll.sum+rr.l);
int scr=max(rr.r,rr.sum+ll.r);
return (hh){scl,scr,max(ll.r+rr.l,max(ll.m,rr.m)),ll.sum+rr.sum};
}
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
build(1,1,n);
cin>>m;
while(m--){
scanf("%d%d%d",&q,&x,&y);
if(q==1) {
if(x>y) swap(x,y);
printf("%d\n",sc(1,1,n,x,y).m);
}
else add(1,1,n,x,y);
}
return 0;
}
然后来讲第二种写法，这是一种离线算法：
我们维护一棵线段树
这棵线段树用于维护区间历史最大值(希望你已经会了，如果不会，你可以自学后再回来，或者等我整理好这块知识）
可以支持的操作为区间加法
从 到 遍历 数组，我们对于每个 ,给区间 加上 a[i]
然后我们来思考遍历到 时 的意义
就是 到 的和
区间 最大值的意义（注意不是历史最大值）就是以 为右端的中的区间最大子段和
那么区间 的历史最大值就是 的区间最大子段和
上代码（这个代码实现的区间最大子段和可以不取）
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M=100010;
struct hh{
int a,b;
int suma,sumb;
}t[M<<2];
struct gg{
int l,r,s;
}b[M];
bool cmp(gg g1,gg g2){
return g1.r<g2.r;
}
int n,m,a[M];
int ans[220000];
void do_sum(int s,int k,int kb){
t[s].b=max(t[s].b,t[s].a+kb);
t[s].sumb=max(t[s].sumb,t[s].suma+kb);
t[s].a+=k;
t[s].suma+=k;
}
void push_up(int s){
t[s].a=max(t[s*2].a,t[s*2+1].a);
t[s].b=max(t[s*2].b,t[s*2+1].b);
}
void push_down(int s){
int ls=s*2,rs=s*2+1;
do_sum(ls,t[s].suma,t[s].sumb);
do_sum(rs,t[s].suma,t[s].sumb);
t[s].suma=t[s].sumb=0;
}
void add(int s,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
do_sum(s,k,k);
return ;
}
push_down(s);
int mid=(l+r)/2;
if(x<=mid) add(s*2,l,mid,x,y,k);
if(y>mid) add(s*2+1,mid+1,r,x,y,k);
push_up(s);
}
int sc(int s,int l,int r,int x,int y){
if(x<=l&&r<=y) return t[s].b;
push_down(s);
int mid=(l+r)/2,op=0;
if(x<=mid) op=max(op,sc(s*2,l,mid,x,y));
if(y>mid) op=max(op,sc(s*2+1,mid+1,r,x,y));
return op;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
cin>>m;
for(int i=1;i<=m;++i) {
scanf("%d%d",&b[i].l,&b[i].r);
b[i].s=i;
}
sort(b+1,b+m+1,cmp);
int k=1;
for(int i=1;i<=m;++i){
for(;k<=b[i].r;++k)
add(1,1,n,1,k,a[k]);
ans[b[i].s]=max(sc(1,1,n,b[i].l,b[i].r),0);
}
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
如果你已经对这个算法有了初步的了解，可以尝试去切一下GSS系列的有关题目