线段树维护区间最大值懒标记问题
  • 板块学术版
  • 楼主Falling_Sakura
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/11 16:12
  • 上次更新2023/11/2 14:29:39
查看原帖
线段树维护区间最大值懒标记问题
773503
Falling_Sakura楼主2023/10/11 16:12

有这样一颗线段树,它维护的是某一个变量(数组)的最大值,初始时线段树为空。

然后每次更新,拿一个值来与线段树的一段区间取 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 子节点,但是修改过后是错误的。

问题出在哪里?

2023/10/11 16:12
加载中...