题解 P4513 【小白逛公园】
ez_lcw
·
·
题解
线段树经典例题
这道题的大意：给出一个动态的区间，以及m次询问，每次询问给出一段区间 [l,r]，要求出这段区间中
和最大的连续序列。
看到这道题的第一反应就是线段树
不会线段树的请出门左转先学一下
但是我们要考虑一下怎么区间合并：
-
首先在结构体（or全局，看个人喜好）定义必有的每个节点的区间 l[] 和 r[]。
-
其次，我们需要为每个节点定义4个数：
$maxright$，以**右端点为尾**的 和最大的连续序列。
$sum$，这段序列的总和
$ans$，这段序列中的最大的连续序列~~（就是答案）~~
3. **如何合并区间呢？（首先注意一点，对于一个节点 $k$，那么它左右儿子的编号分别为 $k*2$、$k*2+1$）**
- 首先，对于 $sum$ 的更新，就比较简单易懂：
$$sum[k]=sum[k*2]+sum[k*2+1];$$
- 其次，对于 $maxleft$ 和 $maxright$ 以及 $ans$ 的更新，我们可以先画个图来感受一下：
样例：
那么将它建成一棵线段树，其中，我们假设根的左儿子和右儿子都已经把 $maxleft$、$maxright$、$sum$、$ans$ 都已计算好了，现在要干的事情是合并区间：
那么我们可以想象一下，根节点的$maxleft$应该是这样的：
同理，$maxright$应该是这样更新的：
那么 $ans$ 的更新也比较容易理解：
$$tree[k].ans=max(max(tree[k*2].ans,tree[k*2+1].ans),tree[k*2].maxright+tree[k*2+1].maxleft);$$
对于 “$maxright[lchild]+maxleft[rchild]$” 的理解，也可以看图来想象：
其实就是左儿子的 $maxright$ 和右儿子的 $maxleft$ 相加，也就是 **和最大的连续序列** 贯穿了左右儿子。
**那为什么不把更新后的 $maxright$ 和 $maxleft$ 加入到 $tree[k].ans$ 的更新里呢？**
其实已经更新了，因为 $ans[lchild]$ 和 $ans[rchild]$ 其实就包含了上面说的 $maxright$、$maxleft$ 更新的第一种情况，即 $tree[k*2].maxleft$和$tree[k*2+1].maxright$。
而 $maxright[lchild]+maxleft[rchild]$ 已经包含了上面说的 $maxright$、$maxleft$ 更新的第二种情况，即 $tree[k*2].sum+tree[k*2+1].maxleft$ 和 $tree[k*2].maxright+tree[k*2+1].sum$。
所以，$tree[k].ans$已经更新了 $maxleft$ 和 $maxright$ 的最优答案。
1. **在询问的时候，也要做一次类似于合并区间的一次寻找最优值，不能直接返回 $max(tree[k*2].ans,tree[k*2+1].ans)$，因为可能询问的区间不完全包含左儿子或右儿子的区间（若完全包含，则不用合并）。**
具体的合并区间代码就是这样了：
```cpp
void putin(int k)
{
tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;//更新sum
tree[k].maxleft=max(tree[k*2].maxleft,tree[k*2].sum+tree[k*2+1].maxleft);//更新maxleft
tree[k].maxright=max(tree[k*2+1].maxright,tree[k*2].maxright+tree[k*2+1].sum);//更新maxright
tree[k].ans=max(max(tree[k*2].ans,tree[k*2+1].ans),tree[k*2].maxright+tree[k*2+1].maxleft);//更新ans
}
```
那么全部的代码如下：
```cpp
#include<cstdio>
#include<iostream>
#define N 2000001
using namespace std;
int n,m;
struct Tree//用结构体来存树
{
int l,r;
long long maxleft,maxright,sum,ans;
}tree[N];
void putin(int k)//合并区间函数
{
tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
tree[k].maxleft=max(tree[k*2].maxleft,tree[k*2].sum+tree[k*2+1].maxleft);
tree[k].maxright=max(tree[k*2+1].maxright,tree[k*2].maxright+tree[k*2+1].sum);
tree[k].ans=max(max(tree[k*2].ans,tree[k*2+1].ans),tree[k*2].maxright+tree[k*2+1].maxleft);
}
void build(int l,int r,int k)//建树
{
tree[k].l=l;tree[k].r=r;
if(l==r)
{
scanf("%lld",&tree[k].sum);
tree[k].maxleft=tree[k].maxright=tree[k].ans=tree[k].sum;//初始化时，因为这个节点只有一个数，maxleft、maxright、sum和ans的值都一样。
return;//别忘了return
}
int mid=(l+r)/2;
build(l,mid,k*2);//递归建树
build(mid+1,r,k*2+1);
putin(k);//合并区间
}
Tree ask(int k,int x,int y)//询问函数，因为每次返回的maxleft等值不一定是左右儿子的数据，所以要返回一个结构体
{
if(x<=tree[k].l&&tree[k].r<=y)
{
return tree[k];
}
int mid=(tree[k].l+tree[k].r)/2;
if(y<=mid) return ask(k*2,x,y);//如果访问的区间全在左儿子里，直接return
else
{
if(x>mid) return ask(k*2+1,x,y);//如果访问的区间全在右儿子里，也直接return
else
{//否则就左右儿子都访问，然后合并区间
Tree t,a=ask(k*2,x,y),b=ask(k*2+1,x,y);
t.maxleft=max(a.maxleft,a.sum+b.maxleft);//做类似的合并区间
t.maxright=max(b.maxright,a.maxright+b.sum);
t.ans=max(max(a.ans,b.ans),a.maxright+b.maxleft);
return t;//返回合并后的区间
}
}
}
void change(int k,int x,int y)//单点修改
{
if(tree[k].l==tree[k].r)
{
tree[k].maxleft=tree[k].maxright=tree[k].ans=tree[k].sum=y;
return;
}
int mid=(tree[k].l+tree[k].r)/2;
if(x<=mid)change(k*2,x,y);//判断目标位置
else change(k*2+1,x,y);
putin(k);//因为值已经改变了，所以要合并区间
}
int main()
{
scanf("%d%d",&n,&m);
build(1,n,1);
while(m--)
{
int choose,x,y;
scanf("%d%d%d",&choose,&x,&y);
if(choose==1)
{
if(x>y)swap(x,y);//这是个坑点，因为题目没有注明x<=y，就是因为这个我调了半天QAQ，最后还是看讨论才知道的，感谢讨论的巨佬们
printf("%lld\n",ask(1,x,y).ans);
}
else
{
change(1,x,y);
}
}
return 0;
}
```
注：感谢我校巨佬@2016gdgzoi471 的题解提供的思路！