线段树懒标记中的 Push Up 操作详解

在线段树（包括带懒标记的线段树）中，‌Push Up（向上更新）‌ 是维护树结构一致性的基础操作。它的核心作用是：‌当子节点的信息发生改变后，利用子节点的最新数据重新计算并更新父节点的聚合信息‌。

虽然懒标记（Lazy Tag）主要解决的是“向下传递修改”的问题，但 Push Up 依然是不可或缺的，因为它负责确保‌从叶子到根的路径上，所有非叶子节点的统计值（如区间和、最大值等）始终与底层数据保持一致‌。

1. 为什么需要 Push Up？

线段树的每个非叶子节点都存储了其对应区间的聚合信息（例如区间和 sum = 左子区间和 + 右子区间和）。

初始状态‌：建树时，我们通过 Push Up 自底向上计算出所有父节点的值。

修改发生后‌：无论是单点修改，还是区间修改中递归到底层后返回，子节点的值都可能发生了变化。

一致性需求‌：如果子节点变了而父节点没变，那么查询包含该父节点的大区间时，得到的结果就是错误的。因此，每次递归回溯时，必须执行 Push Up，将子节点的变更“汇报”给父节点。

注意‌：在带懒标记的区间修改中，如果当前节点被完全覆盖，我们直接更新了当前节点的 sum 并打上 lazy 标记，此时‌不需要‌立即 Push Up，因为当前节点的信息已经是最新的（通过公式直接计算得出）。Push Up 主要发生在‌递归修改了子节点之后‌的回溯阶段。

2. Push Up 的执行逻辑

Push Up 的逻辑非常直观，通常只有一行核心代码，具体取决于维护的信息类型：

场景一：维护区间和（Sum）

父节点的区间和等于左子节点区间和加上右子节点区间和。

parent.sum

=

left.sum

+

right.sum

parent.sum=left.sum+right.sum

场景二：维护区间最大值（Max）

父节点的区间最大值等于左子节点最大值和右子节点最大值中的较大者。

parent.max

=

max

⁡

(

left.max

,

right.max

)

parent.max=max(left.max,right.max)

场景三：维护多种信息

如果节点同时维护总和、最大值、最小值等，Push Up 需要同时更新所有字段。

3. 代码实现示例（C++）

假设线段树节点结构体如下：

cpp

struct Node {

    int l, r;

    long long sum; // 区间和

    long long lazy; // 懒标记

} tr[N * 4];

Push Up 函数实现：‌

cpp

void push_up(int p) {

    // p 是当前父节点编号

    // p<<1 是左子节点，p<<1|1 是右子节点

    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;

    // 如果还维护了最大值，则加上：

    // tr[p].max_val = max(tr[p << 1].max_val, tr[p << 1 | 1].max_val);

}

4. Push Up 在完整流程中的调用时机

为了清晰理解 Push Up 的位置，我们看它在‌区间修改‌和‌单点修改‌中的具体调用点：

A. 在区间修改（Modify/Update）中

cpp

void modify(int p, int l, int r, int val) {

    // 1. 如果当前节点区间完全被覆盖

    if (tr[p].l >= l && tr[p].r <= r) {

        tr[p].sum += (long long)val * (tr[p].r - tr[p].l + 1);

        tr[p].lazy += val;

        return; // 直接返回，无需 Push Up，因为当前节点已手动更新

    }

    // 2. 部分覆盖，需要下传标记并递归子节点

    push_down(p); 

    int mid = (tr[p].l + tr[p].r) >> 1;

    if (l <= mid) modify(p << 1, l, r, val);

    if (r > mid)  modify(p << 1 | 1, l, r, val);

    // 3. 【关键】递归结束后，子节点可能已改变，必须 Push Up 更新当前节点

    push_up(p); 

}

B. 在单点修改中

cpp

void update_point(int p, int idx, int val) {

    if (tr[p].l == tr[p].r) {

        tr[p].sum = val;

        return;

    }

    push_down(p); // 如果有懒标记，先下传

    int mid = (tr[p].l + tr[p].r) >> 1;

    if (idx <= mid) update_point(p << 1, idx, val);

    else            update_point(p << 1 | 1, idx, val);

    // 【关键】回溯时更新父节点

    push_up(p);

}

5. Push Up 与 Push Down 的区别总结

表格

特性 Push Up (向上更新) Push Down (向下下发)

方向‌ 子节点 

→

→ 父节点 父节点 

→

→ 子节点

目的‌ 保持父节点聚合信息与子节点同步 将父节点的待处理修改传递给子节点

触发时机‌ 递归修改子节点‌之后‌（回溯时） 递归访问子节点‌之前‌（深入时）

依赖关系‌ 依赖子节点的最新 sum/max 等值 依赖父节点的 lazy 标记

复杂度‌

𝑂

(

1

)

O(1)

𝑂

(

1

)

O(1)

6. 常见误区

忘记 Push Up‌：在递归修改子节点后，如果忘记调用 push_up(p)，父节点的值将保持旧状态，导致后续查询结果错误。

在完全覆盖时多余 Push Up‌：当区间完全覆盖当前节点时，我们直接更新了 tr[p].sum 并打了标记，此时直接 return 即可。如果在 return 前强行调用 push_up，反而会用尚未更新的子节点旧值覆盖掉刚刚计算好的正确值，导致错误。

混淆 Push Up 和 Push Down 的顺序‌：记住口诀——‌“下去之前 Push Down，回来之后 Push Up”‌。

总结

Push Up 是线段树维持数据正确性的“基石”。在带懒标记的线段树中，它确保了那些‌没有被懒标记直接覆盖、而是通过递归深入修改的子区间‌的变化，能够正确地反映到上层节点中。没有 Push Up，线段树就无法在动态修改中保持区间信息的准确性。