为啥update时要对懒标记判断后pushdown一次,然后query的时候也要对懒标记判断后pushdown一次,我一开始只有在query时判断了,并没有在update时判断,想了好久没有想出为什么,麻烦大佬解答。 update
void update(int L, int R, int rt, int add)
{
if(L > tree[rt].r || R < tree[rt].l)
{
return;
}
if(L <= tree[rt].l && R >= tree[rt].r)
{
tree[rt].lazy += add;
tree[rt].sum += (tree[rt].r - tree[rt].l + 1) * add;
return;
}
if(tree[rt].lazy > 0)
{
pushdown(rt);
}
//就是这个if判断开始没写,看了题解后补上去就AC了,不太理解
update(L, R, rt<<1,add);
update(L, R, rt<<1|1,add);
pushup(rt);
}
query代码
long long query_tree(int L, int R, int rt)
{
if(tree[rt].l >= L && tree[rt].r <= R)
{
return tree[rt].sum;
}
if(tree[rt].l > R || tree[rt].r < L)
return 0;
if(tree[rt].lazy > 0)
pushdown(rt);
//这里我知道要写的,就是不知道为啥上面也需要写这个if判断
return query_tree(L, R, rt<<1)+query_tree(L, R, rt<<1|1);
}