线段树小例题——结合前后缀获得结果

本文主要是介绍线段树小例题——结合前后缀获得结果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

和我今天上午写的那个前后缀太像了，不能说一模一样，但是至少我觉得思路是真的一点没变

上一道题的链接：http://t.csdnimg.cn/pXBnU

P4513 小白逛公园 

题意：有n个点，每个点都有一个初值，然后有m个操作，分为两种 ，一种是修改操作，可以修改单点的值，还有一种操作会告诉你范围，让你找出范围内最大的连续公园

思路：如果你有幸看过上面那个题解，恭喜你，这一边又可以巩固一遍了 

这题我们还是类似于前后缀，但是变成了前缀和和后缀和，那么我们线段树的变量该怎么去设置呢？
maxn表示的是区间的最大值，maxl表示从左端点开始区间的最大值，maxr表示从右端点开始区间的最大值，sum表示整个区间的和

我们在选取区间最大值的时候

处理左右孩子的连接处：首先需要去判断左孩子的maxr和右孩子的maxl的值是否都是小于0的，如果都小于0，那么久从中取出最小的作为当前结点的最大值，如果都是正数，那么哪部分是正的哪部分就加进去

然后就是正常处理

当前结点的最大值和左右孩子的最大值相比，选出最大的作为当前结点的最大值

当前结点以左端点开始开始的最大值=左孩子的左端点为起始点的最大值和左孩子的和+右孩子以左端点为起始的最大值 

当前结点的右端点同理

在查询的时候

1、如果查询区间覆盖这一节点，将该节点信息返回。

2、如果只与一个儿子有交集，就返回在那个儿子中查找到的信息。

3、如果与两个儿子都有交集，就先分别计算出两个儿子的信息，然后按修改的方式将两个信息合并，然后返回。

4、最后返回的max值即为答案。

因此就可以写出代码了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int num[500005];
struct node{int l,r;int maxn;int maxl;int maxr;int sum;
}tree[500005*4];
int flag;
int a,b;void pushdown(node &t, const node &lt, const node &rt)
{if (lt.maxr < 0 && rt.maxl < 0){t.maxn = max(lt.maxr, rt.maxl);}else{t.maxn = 0;if (lt.maxr > 0){t.maxn += lt.maxr;}if (rt.maxl > 0){t.maxn += rt.maxl;}}t.maxn = max(t.maxn, max(lt.maxn, rt.maxn));t.maxl = max(lt.maxl, lt.sum + rt.maxl);t.maxr = max(rt.maxr, rt.sum + lt.maxr);t.sum = lt.sum + rt.sum;
}
void build(int i,int l,int r)
{tree[i].l=l;tree[i].r=r;if(l==r){tree[i].maxn=tree[i].maxl=tree[i].maxr=tree[i].sum=num[l];return ;}int mid=(l+r)/2;build(i*2,l,mid);build(i*2+1,mid+1,r);pushdown(tree[i], tree[i * 2], tree[i * 2 + 1]);
}void change(int i,int dis,int k)
{if(tree[i].l==tree[i].r){tree[i].sum=tree[i].maxn=tree[i].maxl=tree[i].maxr=k;return ;}int mid=(tree[i].l+tree[i].r)/2;if(dis<=mid){change(i*2,dis,k);}else{change(i*2+1,dis,k);}pushdown(tree[i],tree[i * 2],tree[i * 2 + 1]);
}node find(int i,int l,int r)
{if(tree[i].l>=l&&tree[i].r<=r){return tree[i];}int mid=(tree[i].l+tree[i].r)/2;if(l<=mid&&mid+1<=r){node rt;pushdown(rt,find(i*2,l,r),find(i*2+1,l,r));return rt;}else if(l<=mid){return find(i*2,l,r);}else{return find(i*2+1,l,r);}
}signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>num[i];}build(1,1,n);for(int i=1;i<=m;i++){cin>>flag>>a>>b;if(flag==1){if(a>b)swap(a,b);cout<<find(1,a,b).maxn<<"\n";}else{change(1,a,b);}}return 0;
}

 

这篇关于线段树小例题——结合前后缀获得结果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---