弱鸡在写代码时关于懒标记有些不懂,望大佬解答
查看原帖
弱鸡在写代码时关于懒标记有些不懂,望大佬解答
53131
MathsCode楼主2020/9/2 20:05

为啥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);
}
2020/9/2 20:05
加载中...