有这样一颗线段树,它维护的是某一个变量(数组)的最大值,初始时线段树为空。
然后每次更新,拿一个值来与线段树的一段区间取 max:
void update(int u, int l, int r, int k)
{
if(l <= tr[u].l && tr[u].r <= r)
{
tr[u].tmax = max(tr[u].tmax, k);
tr[u].tag = max(tr[u].tag, k);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) update(u << 1, l, r, k); //
if(r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}
它的 pushdown 是这样的:
void pushdown(int u)
{
Node &root = tr[u];
if(root.tag)
{
ls(u).tmax = max(ls(u).tmax, root.tag);
rs(u).tmax = max(rs(u).tmax, root.tag);
ls(u).tag = max(ls(u).tag, root.tag);
rs(u).tag = max(rs(u).tag, root.tag);
root.tag = 0;
}
}
然后我就想,能不能不要懒标记了,拿父节点的 tmax 来 pushdown 子节点,但是修改过后是错误的。
问题出在哪里?