想问一下为什么49行不写也可以AC

为什么第49行不写也可以AC,递归到最底层上来之后,不进行这部操作后来的Sum不就不对了吗。。。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5e5+5;

int tree[N<<2],lmax[N<<2],rmax[N<<2],sum[N<<2];
struct T
{
int ans,ll,rr,Sum;
};

void push_up(int rt)
{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
lmax[rt] = max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
rmax[rt] = max(rmax[rt<<1|1],sum[rt<<1|1]+rmax[rt<<1]);
tree[rt] = max(max(tree[rt<<1],tree[rt<<1|1]),lmax[rt<<1|1]+rmax[rt<<1]);
}

void update(int p,int x,int rt,int l,int r)
{
if (l==r){
tree[rt] = lmax[rt] = rmax[rt] = sum[rt] = x;
return ;
}
int m = l+r>>1;
if (p<=m) update(p,x,rt<<1,l,m);
else update(p,x,rt<<1|1,m+1,r);
push_up(rt);
}

T query(int L,int R,int rt,int l,int r) ///求区间L~R的最大区间和
{
if (L==l && r==R){
T sb = (T){tree[rt],lmax[rt],rmax[rt],sum[rt]};
return sb;
}
int m = l+r>>1;
if (L>m) return query(L,R,rt<<1|1,m+1,r); ///表明要取的区间在其中一半,只取这一半分析就够了
else if (R<=m) return query(L,R,rt<<1,l,m);
///表明沿着终点两边都有,左边一半算所求区间左边一部分的,右算右
T a,b,c;
a = query(L,m,rt<<1,l,m);
b = query(m+1,R,rt<<1|1,m+1,r);
c.ans = max(max(a.ans,b.ans),a.rr+b.ll);
c.ll = max(a.ll,a.Sum+b.ll);
c.rr = max(b.rr,b.Sum+a.rr);
//c.Sum = a.Sum + b.Sum;///这句话为什么可以不加?
return c;
}

void build(int rt,int l,int r)
{
if (l==r){
int x;
scanf("%d",&x);
tree[rt] = lmax[rt] = rmax[rt] = sum[rt] = x;
return ;
}
int m = l+r>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
push_up(rt);
}

int main()
{
int n,q;
scanf("%d %d",&n,&q);
build(1,1,n);
while(q--){
int ty,a,b;
scanf("%d %d %d",&ty,&a,&b);
if (ty==1){
if (a>b) swap(a,b);
printf("%d\n",query(a,b,1,1,n).ans);
}
else {
update(a,b,1,1,n);
}
}
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1083
难度
7
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
5009
已通过
976
通过率
19%
被复制
6
上传者