C++ 代码
/*
本题希望完成两个操作:
1.单点修改,将a[x]的值改成y
2.查询区间[x,y]之间的最大连续子段和tmax
父节点的tmax怎么由子节点得到呢?
以下三种情况取最大值
1.左孩子的最大连续子段和tr[u<<1].tmax
2.右孩子的最大连续子段和tr[u<<1|1].tmax
3.左孩子的右端点向左的最大连续子段和+右孩子的左端点向右的最大连续子段和
tr[u<<1].rmax+tr[u<<1|1].lmax
那么每个节点Node就需要存储区间[l,r]内的以下信息:
l,r,tmax,lmax,rmax
父节点的lmax和rmax怎么由子节点得到呢?
lmax=max(tr[u<<1].lmax,左儿子节点区间内的和sum+tr[u<<1|1].lmax)
rmax=max(tr[u<<1].rmax,右儿子节点区间内的和sum+tr[u<<1].rmax)
(因为存在负数的原因,sum不一定就大于部分和)
所以node之中还需要一个sum信息,来保存[l,r]区间内的所有数的和
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int w[N];
int n,m;
struct Node{
int l,r;
int sum;
int tmax,lmax,rmax;
}tr[4*N];
void pushup(Node &u,Node &l,Node &r)
{
u.sum=l.sum+r.sum;
u.lmax=max(l.lmax,l.sum+r.lmax);
u.rmax=max(r.rmax,l.rmax+r.sum);
u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.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[r],w[r],w[r],w[r]};
else
{
tr[u]={l,r};
int mid=(l+r)/2;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v)//单点修改x位置上的值
{
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)/2;
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(tr[u].l>=l && tr[u].r<=r) return tr[u];
else
{
int mid=(tr[u].l+tr[u].r)/2;
if(r<=mid) return query(u<<1,l,r);//查询的区间完全在左边
else if(l>mid) return query(u<<1|1,l,r);//查询的区间完全在右边
else//横跨左右两边,就要看左边最大,右边最大,左边后缀+右边前缀三个的最大值
{
Node left=query(u<<1,l,r);
Node right=query(u<<1|1,l,r);
Node res;
pushup(res,left,right);
return res;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
while (m -- )
{
int op,x,y;
cin>>op>>x>>y;
if(op==1)
{
if(x>y) swap(x,y);
cout<<query(1,x,y).tmax<<endl;
}
else
{
modify(1,x,y);
}
}
return 0;
}