区间最大子段和问题

frzFRZ · 2025-08-08 09:37:13 · 算法·理论

问题

给定一个数列 a_1,a_2,a_3,...,a_n
有 m 次询问，每次询问给你两个数 l,r
你需要求出 a_l \sim a_r 的最大子段和

做法

1.暴力统计

对于每一个区间 [l,r]，枚举左端点和右端点，求所有区间的最大值，复杂度为 O(mn^2)

2.动态规划

我们可以一次性算出所有区间的最大子段和，然后直接输出答案
规定：

假设一个区间为 [l,r] ,将它分成两段，两个子段的信息已经处理完成
显然有：

\

\ 右区间同理

\

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,val[N];
long long ls[N][N],rs[N][N],ms[N][N],s[N][N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=1;i<=n;i++) ls[i][i]=rs[i][i]=ms[i][i]=s[i][i]=val[i];
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            int mid=(l+r)>>1;
            s[l][r]=s[l][mid]+s[mid+1][r];
            ls[l][r]=max(ls[l][mid],ls[mid+1][r]+s[l][mid]);
            rs[l][r]=max(rs[mid+1][r],rs[l][mid]+s[mid+1][r]);
            ms[l][r]=max(ls[mid+1][r]+ls[l][mid],max(ms[l][mid],ms[mid+1][r]));
        }
    }
    cin>>m;
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        cout<<ms[l][r]<<"\n";
    }
    return 0;
}

复杂度为 O(n+m)

线段树

例题：SP1716
若数列 a 会修改，动态规划就不能求解
这时我们可以用线段树来维护，可单点修改、区间查询

#include<bits/stdc++.h>
#define ll long long
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N=1e5+10;
const ll inf=2e18;
int n,m;
struct node
{
    ll ls,rs;
    ll ms;
    ll s;
}tr[4*N];
void pushup(int rt)
{
    tr[rt].s=tr[lc].s+tr[rc].s;
    tr[rt].ls=max(tr[lc].ls,tr[rc].ls+tr[lc].s);
    tr[rt].rs=max(tr[rc].rs,tr[lc].rs+tr[rc].s);
    tr[rt].ms=max(tr[lc].rs+tr[rc].ls,max(tr[lc].ms,tr[rc].ms));
    return ;
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        cin>>tr[rt].s;
        tr[rt].ls=tr[rt].rs=tr[rt].ms=tr[rt].s;
        return ;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(rt);
    return ;
}
void update(int rt,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tr[rt].s=tr[rt].ls=tr[rt].rs=tr[rt].ms=val;
        return ;
    }
    if(pos<=mid) update(lc,l,mid,pos,val);
    else update(rc,mid+1,r,pos,val);
    pushup(rt);
    return ;
}
node query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tr[rt];
    node x,y,w;
    if(R<=mid) w=query(lc,l,mid,L,R);
    else if(L>mid) w=query(rc,mid+1,r,L,R);
    else
    {
        x=query(lc,l,mid,L,mid);
        y=query(rc,mid+1,r,mid+1,R);
        w.s=x.s+y.s;
        w.ls=max(x.ls,x.s+y.ls);
        w.rs=max(y.rs,y.s+x.rs);
        w.ms=max(x.rs+y.ls,max(x.ms,y.ms));
    }
    return w;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    build(1,1,n);
    cin>>m;
    int opt,l,r,pos,val;
    while(m--)
    {
        cin>>opt;
        if(opt==0)
        {
            cin>>pos>>val;
            update(1,1,n,pos,val);
        }
        else
        {
            cin>>l>>r;
            node ans=query(1,1,n,l,r);
            cout<<ans.ms<<"\n";
        }
    }
    return 0;
}

复杂度为 O(n+mlogn)