题目链接：https://www.luogu.org/problem/P4513
题目大意：单点修改和求区间最大连续字段和
解题思路：很容易想到是用线段树来做，但是如何进行维护呢？
每个维护区间 [L,R]的节点内我们需要维护以下信息：
sum：[L,R]的区间和
lm：从左端点 L开始的最大子段和（简称左子段和）
rm:从右端点 R 开始的最大子段和（简称右子段和）
ans:[L,R] 内的最大子段和
注意：询问区间跨过mid时要合并一下答案，思路与pushup函数中的差不多
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=500000+7; int n,m,a[maxn]; struct node{ int lm,rm,sum,ans; }tree[maxn*4]; void pushup(int rt){ tree[rt].lm=max(tree[rt<<1].lm,tree[rt<<1].sum+tree[rt<<1|1].lm); tree[rt].rm=max(tree[rt<<1|1].rm,tree[rt<<1|1].sum+tree[rt<<1].rm); tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; tree[rt].ans=max(max(tree[rt<<1].ans,tree[rt<<1|1].ans),tree[rt<<1].rm+tree[rt<<1|1].lm); } void build(int l,int r,int rt){ if(l==r){ tree[rt].lm=tree[rt].rm=tree[rt].sum=tree[rt].ans=a[l]; return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); } void update(int pos,int val,int l,int r,int rt){ if(l==r){ tree[rt].lm=tree[rt].rm=tree[rt].sum=tree[rt].ans=val; return; } int mid=(l+r)>>1; if(pos<=mid) update(pos,val,l,mid,rt<<1); else update(pos,val,mid+1,r,rt<<1|1); pushup(rt); } node query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return tree[rt]; //区间完全覆盖，直接返回该节点 int mid=(l+r)>>1; if(R<=mid) return query(L,R,l,mid,rt<<1); //只在左区间，直接查询左区间 else if(L>mid) return query(L,R,mid+1,r,rt<<1|1); //只在右区间，直接查询右区间 else{ //左右区间都有，考虑如何合并 //res1记录左覆盖区间，res2记录右覆盖区间 node res,res1=query(L,mid,l,mid,rt<<1),res2=query(mid+1,R,mid+1,r,rt<<1|1); res.lm=max(res1.lm,res1.sum+res2.lm); res.rm=max(res2.rm,res2.sum+res1.rm); res.ans=max(max(res1.ans,res2.ans),res1.rm+res2.lm); return res; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); while(m--){ int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1){ if(x>y) swap(x,y); printf("%d\n",query(x,y,1,n,1).ans); }else update(x,y,1,n,1); } return 0; }
原文：https://www.cnblogs.com/zjl192628928/p/11438270.html