关于线段树懒惰标记的问题以及pushdown函数的写法
  • 板块学术版
  • 楼主xia0ji233
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/4/2 15:17
  • 上次更新2023/11/5 01:10:16
查看原帖
关于线段树懒惰标记的问题以及pushdown函数的写法
119638
xia0ji233楼主2021/4/2 15:17

我也不知道是不是我的问题,我在做线段树区间加法的时候都是直接给懒惰标记,然后pushdown就处理那一点的懒惰标记,然后判断叶结点决定给不给两个儿子。

但是我看大部分标程都是这么写的

inline void pushdown(int rt,int lenn){//这里是对两个儿子进行加法操作
    tree[rt<<1].lazy+=tree[rt].lazy;
    tree[rt<<1|1].lazy+=tree[rt].lazy;
    tree[rt<<1].sum+=tree[rt].lazy*(lenn-(lenn>>1));
    tree[rt<<1|1].sum+=tree[rt].lazy*(lenn>>1);
    tree[rt<<1].sum%=mod;
    tree[rt<<1|1].sum%=mod;
    tree[rt].lazy=0;
}
inline void update(int rt,int l,int r,int L,int R,int k){
    if(L>r||R<l)return;
    if(L<=l&&r<=R){
        tree[rt].lazy+=k;
        tree[rt].sum+=k*len;//区别
    }
    else{
        update(lson,L,R,k);
        update(rson,L,R,k);
        tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%mod;
    }
}

这样子的写法我承认没有问题,但是我的我认为也没有什么问题吧。

inline void push_down(int i){
    if(tree[i].lazy_tag){
        tree[i].value+=(tree[i].r-tree[i].l+1)*tree[i].lazy_tag;
        if(tree[i].l!=tree[i].r){
            tree[i<<1].lazy_tag+=tree[i].lazy_tag;
            tree[i<<1|1].lazy_tag+=tree[i].lazy_tag;
        }
        tree[i].lazy_tag=0;
    }
}
inline void add_area(int i,int l,int r,int k){
    if(tree[i].r<l||tree[i].l>r)return;//如果不在区间内,则不进行任何操作 
    if(tree[i].l>=l&&tree[i].r<=r){//如果区间被包含 
        tree[i].lazy_tag+=k;
        return;
    }
    if(tree[i].l<=l&&tree[i].r>=r){//如果区间直接包含,则进行类似操作 
        tree[i].value+=k*(r-l+1);
    } 
    else if(l>=tree[i].l){//如果右区间重合
        tree[i].value+=k*(tree[i].r-l+1);
    }
    else{//如果区间右重合 
        tree[i].value+=k*(r-tree[i].l+1);
    }
    add_area(i<<1,l,r,k);//儿子进行类似操作 
    add_area(i<<1|1,l,r,k);
}

因为我是直接从标程上copy下来的,所以某些函数名没有改的一样,求各位大佬指正我这么传懒惰标记会发生什么错误?蒟蒻在做树剖题的时候只因为懒惰标记写的有很大区别导致过不去qwq

2021/4/2 15:17
加载中...