MENU

线段树区间修改优先级

2019-06-26 • 阅读: 21 • 数据结构—线段树阅读设置

线段树一个区间进行多个操作时处理的优先级

** 懒惰标记:当前区间已经修改,但儿子节点区间未修改,不能误认为当前区间也未修改。**

一 、 区间赋值和区间

这个很明显就是赋值的优先级高,下放懒惰标记时,我们做出如下讨论。

  • 当前区间有赋值标记时,对儿子区间进行赋值,同时标记传给儿子,把当前区间以及儿子区间的加标记清除
  • 当前区间无懒惰标记,但有加标记,对儿子区间进行修改,同时标记下传, 下传时注意。若儿子区间有赋值标记,此时需要将儿子区间的赋值标记加上当前的加标记的值,同时将可儿子区间加标记清除。若儿子区间无赋值标记,直接将加标记下传即可。

修改也有如下讨论

  • 执行赋值修改时,区间打上赋值标记时,将加标记清除
  • 执行加值修改时,如当前区间有赋值标记,则在赋值标记上加上当前的加值,若无赋值标记,区间上加值标记即可。

void PushDown(int rt){
    if (changetag[rt] != -1){
        Max[rt<<1] = changetag[rt]; Max[rt<<1|1] = changetag[rt];
        changetag[rt << 1] = changetag[rt]; addtag[rt << 1] = 0;
        changetag[rt << 1 | 1] = changetag[rt]; addtag[rt << 1 | 1] = 0;
        changetag[rt] = -1;
    }else if (addtag[rt]){
        Max[rt<<1] += addtag[rt]; Max[rt<<1|1] += addtag[rt];
        if (changetag[rt<<1] != -1) changetag[rt<<1] += addtag[rt];
        else addtag[rt<<1] += addtag[rt];
        if (changetag[rt<<1|1] != -1) changetag[rt<<1|1] += addtag[rt];
        else addtag[rt<<1|1] += addtag[rt];
        addtag[rt] = 0;        
    }
}
void add(int rt, int l, int r, int L, int R, int C)
{
    if (L <= l && r <= R){
        Max[rt] = Max[rt] + C;
        if (changetag[rt] == -1) addtag[rt] += C;
        else changetag[rt] += C;
        return;
    }
}
void change()
{
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码