线段树中的懒标记(Lazy-Tag)-MuQYY的博客

1. 引言

在基础的线段树中，我们可以通过 $O(\log n)$ 的时间复杂度来完成单点更新和区间查询。然而，当需要对整个区间进行更新（如将区间 $[L, R]$ 的所有元素增加一个值 $d$）时，如果我们逐一更新相关的节点，会导致时间复杂度增加。为了解决这个问题，我们使用懒标记（Lazy Tag）技术。

2. 什么是懒标记？

懒标记是一种延迟更新策略：

当我们需要更新一个区间的值时，不立即递归更新所有受影响的节点。
而是将要更新的信息标记在当前节点上，等到真正需要用到这些信息时（如查询操作），才进行更新。

3. 为什么使用懒标记？

提高更新效率：避免不必要的递归更新，只有在必要时才更新子节点。
支持区间更新：允许在 $O(\log n)$ 的时间内完成区间更新。
降低查询成本：查询时只需将懒标记向下传播即可，保持整体复杂度为 $O(\log n)$。

4. 线段树的懒标记结构

在使用懒标记的线段树中，我们为每个节点维护：

tree[node]：存储该节点代表的区间的值（如区间和、区间最值）。
lazy[node]：存储当前节点的懒标记（表示待更新的增量）。

5. 核心操作

5.1 Push Down：标记下传

当查询或更新时，需要将当前节点的懒标记向其左右子节点传递，并清空当前节点的懒标记。

5.2 Push Up：节点更新

更新节点时，根据左右子节点的值更新当前节点。

6. 代码实现：区间更新 + 区间查询

#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;
int tree[4 * N];   // 线段树数组，存储区间和
int lazy[4 * N];   // 懒标记数组

// Push Down：将当前节点的懒标记传递给左右子节点
void push_down(int node, int l, int r) {
    if (lazy[node] != 0) {  // 如果当前节点有懒标记
        int mid = (l + r) / 2;

        // 将懒标记传播给左右子节点
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];

        // 更新左右子节点的值
        tree[2 * node] += lazy[node] * (mid - l + 1);
        tree[2 * node + 1] += lazy[node] * (r - mid);

        // 清空当前节点的懒标记
        lazy[node] = 0;
    }
}

// Push Up：更新当前节点的值
void push_up(int node) {
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

// 构建线段树，节点 node 负责区间 [l, r]
void build(int node, int l, int r, const vector& A) {
    if (l == r) {
        tree[node] = A[l];  // 叶节点存储原数组的值
    } else {
        int mid = (l + r) / 2;
        build(2 * node, l, mid, A);       // 构建左子树
        build(2 * node + 1, mid + 1, r, A);  // 构建右子树
        push_up(node);  // 更新当前节点的值
    }
}

// 区间更新，将区间 [L, R] 的每个元素增加 delta
void update_range(int node, int l, int r, int L, int R, int delta) {
    if (L <= l && r <= R) {  // 当前节点的区间完全包含在 [L, R] 中
        tree[node] += delta * (r - l + 1);  // 更新区间和
        lazy[node] += delta;  // 标记懒更新
    } else {
        push_down(node, l, r);  // 下传懒标记
        int mid = (l + r) / 2;
        if (L <= mid) update_range(2 * node, l, mid, L, R, delta);  // 更新左子树
        if (R > mid) update_range(2 * node + 1, mid + 1, r, L, R, delta);  // 更新右子树
        push_up(node);  // 更新当前节点的值
    }
}

// 区间查询，查询区间 [L, R] 的和
int query_range(int node, int l, int r, int L, int R) {
    if (L <= l && r <= R) {  // 当前节点的区间完全包含在 [L, R] 中
        return tree[node];
    } else {
        push_down(node, l, r);  // 下传懒标记
        int mid = (l + r) / 2;
        int sum = 0;
        if (L <= mid) sum += query_range(2 * node, l, mid, L, R);  // 查询左子树
        if (R > mid) sum += query_range(2 * node + 1, mid + 1, r, L, R);  // 查询右子树
        return sum;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    vector A(n + 1);  // 原数组
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
    }

    build(1, 1, n, A);  // 构建线段树

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {  // 区间更新
            int L, R, delta;
            cin >> L >> R >> delta;
            update_range(1, 1, n, L, R, delta);
        } else if (type == 2) {  // 区间查询
            int L, R;
            cin >> L >> R;
            cout << query_range(1, 1, n, L, R) << endl;
        }
    }

    return 0;
}

7. 代码解析

构建线段树：
- 使用递归构建线段树，叶节点存储数组元素，内部节点存储子区间的和。
区间更新：
- 当更新的区间完全包含当前节点的区间时，直接更新当前节点的值，并打上懒标记。
- 如果当前节点的区间与更新区间部分重叠，则下传懒标记，并递归更新左右子树。
区间查询：
- 查询时需要先下传懒标记，保证查询到的值是最新的。