题解 P4513 【小白逛公园】

· · 题解

线段树经典例题

这道题的大意：给出一个动态的区间，以及m次询问，每次询问给出一段区间 [l,r]，要求出这段区间中 和最大的连续序列。

看到这道题的第一反应就是线段树 不会线段树的请出门左转先学一下

但是我们要考虑一下怎么区间合并：

  1. 首先在结构体（or全局，看个人喜好）定义必有的每个节点的区间 l[] 和 r[]。

  2. 其次，我们需要为每个节点定义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 的最优答案。

  4. 在询问的时候，也要做一次类似于合并区间的一次寻找最优值，不能直接返回 max(tree[k*2].ans,tree[k*2+1].ans)，因为可能询问的区间不完全包含左儿子或右儿子的区间（若完全包含，则不用合并）。

具体的合并区间代码就是这样了：

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
}

那么全部的代码如下：

#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 的题解提供的思路！