求助
  • 板块学术版
  • 楼主ZYStream
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/21 19:59
  • 上次更新2025/1/21 22:13:32
查看原帖
求助
1419923
ZYStream楼主2025/1/21 19:59

这是oi-wiki上的线段树的区间修改的代码,其中下传懒标记的代码为什么会被执行,但b[p]被标记时不就直接return了吗,下面不就不会再递归子节点了吗

// [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p
// 为当前节点的编号
void update(int l, int r, int c, int s, int t, int p) {
  // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (b[p] && s != t) {
    // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
    b[p] = 0;                                // 清空当前节点的标记
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}
中间第10-15行代码为什么会被执行 
2025/1/21 19:59
加载中...