关于线段树懒惰标记
  • 板块学术版
  • 楼主wowwowwow
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/10/7 14:27
  • 上次更新2023/10/27 08:19:43
查看原帖
关于线段树懒惰标记
373938
wowwowwow楼主2022/10/7 14:27

为什么修改时要把懒标记给子节点,感觉可以自己存着,然后等查询时再下放标记

void modify(int p, int l, int r, int a, int b, int v){ //a~b += v
    if(a > r || b < l) return;
    if(a <= l && r <= b){
        add[p] += v;
        sum[p] += (r - l + 1) * v;
        return ;
    }
    pushdown(p, l, r); //为什么这里要将标记给子结点?
    int mid = (l + r) >> 1;
    modify(p << 1, l, mid, a, b, v);
    modify(p << 1 | 1, mid + 1, r, a, b, v); 
    sum[p] = sum[p << 1] + sum[p << 1 | 1];
}

2022/10/7 14:27
加载中...