slowbyte
首页友链关于

线段树详解

发表于 2025-07-16 7773 字 39 min read

文章目录
线段树模板
线段树的原理、建树、区间修改与查询、懒标记，以及常见变式。

本篇对应源码见仓库 solutions/xcpc/algorithm/ds/segment-tree/。

线段树（Segment Tree）详解

什么是线段树？

线段树，顾名思义，就是一棵“树”，它用来处理“线段”上的问题。更准确地说，它是一种数据结构，用于高效地处理区间查询和区间修改。

想象一下你有一个数组 A，你想知道某个区间 [L, R] 内元素的和，或者把某个区间 [L, R] 内的每个元素都加上一个值 X。如果只是简单地遍历数组，查询和修改都需要 O(N) 的时间复杂度。当 N 很大，操作次数很多时，就会非常慢。线段树就是为了解决这个问题而生的。

线段树的核心思想：分治

线段树的核心思想是分治（Divide and Conquer）。它把一个大区间分成两个小区间，再把小区间继续分成更小的区间，直到每个区间都只包含一个元素。这样，整个数组就被组织成了一棵二叉树的结构。

每个节点都代表一个区间。

  • 根节点代表整个大区间（例如 [0, N-1]）。
  • 左孩子代表其父节点区间的左半部分。
  • 右孩子代表其父节点区间的右半部分。
  • 叶子节点代表长度为1的区间（即数组中的一个元素）。

线段树的结构

我们用一个数组来存储线段树。如果原始数组有 N 个元素，那么线段树通常需要 2N 到 4N 的空间（因为它是完全二叉树，最后一层叶子节点可能不完全填满，为了方便计算父子关系，我们通常分配更多空间）。

假设原始数组 A 的索引范围是 [0, N-1]。

  • 根节点的索引可以是1（方便计算左右子节点）。
  • 如果一个节点的索引是 p，那么它的左孩子是 2p，右孩子是 2p+1。

每个节点需要存储它所代表区间的某种信息，比如：

  • 区间和
  • 区间最大值
  • 区间最小值
  • 其他需要维护的信息，取决于具体问题

线段树的构建（Build）

构建线段树的过程是一个递归的过程。

build(node_idx, start, end)：

  1. 基准情况（叶子节点）：如果 start == end，说明当前节点代表一个单一元素。将 tree[node_idx] 设置为 A[start]（或者 A[end]）。
  2. 递归构建子树：
    • 计算 mid = (start + end) / 2。
    • 递归构建左子树：build(2 * node_idx, start, mid)。
    • 递归构建右子树：build(2 * node_idx + 1, mid + 1, end)。
  3. 合并信息：
    • tree[node_idx] 的值由其左右子节点的值合并而来。例如，如果是求区间和，tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1]。

时间复杂度：O(N)。因为每个节点只被访问一次，并且进行常数次操作。

线段树的查询（Query）

查询一个区间 [query_start, query_end] 的信息。

query(node_idx, current_start, current_end, query_start, query_end)：

  1. 完全包含：如果当前节点代表的区间 [current_start, current_end] 完全包含在查询区间 [query_start, query_end] 内（即 query_start <= current_start 且 current_end <= query_end），那么直接返回 tree[node_idx] 的值。
  2. 完全不相交：如果当前节点代表的区间 [current_start, current_end] 和查询区间 [query_start, query_end] 完全不相交，返回一个“空值”（例如，求和时返回0，求最大值时返回负无穷）。
  3. 部分相交：如果部分相交，就需要递归地查询左右子树，并将结果合并。
    • 计算 mid = (current_start + current_end) / 2。
    • 递归查询左子树：left_result = query(2 * node_idx, current_start, mid, query_start, query_end)。
    • 递归查询右子树：right_result = query(2 * node_idx + 1, mid + 1, current_end, query_start, query_end)。
    • 将 left_result 和 right_result 合并后返回。

时间复杂度：O(logN)。因为每次递归都会将区间减半，最多访问 logN 层。在每一层，最多访问常数个节点（通常是2个）。

线段树的修改（Update）

修改一个区间 [update_start, update_end] 的信息（例如，将某个区间的每个元素都加上一个值）。

单点修改（Point Update）： 修改数组中 A[idx] 的值。

update(node_idx, current_start, current_end, update_idx, new_value)：

  1. 基准情况（找到叶子节点）：如果 current_start == current_end，并且 current_start == update_idx，说明找到了要修改的叶子节点。更新 tree[node_idx] = new_value。
  2. 递归修改子树：
    • 计算 mid = (current_start + current_end) / 2。
    • 如果 update_idx <= mid，说明修改的元素在左子树，递归 update(2 * node_idx, current_start, mid, update_idx, new_value)。
    • 否则，说明修改的元素在右子树，递归 update(2 * node_idx + 1, mid + 1, current_end, update_idx, new_value)。
  3. 更新当前节点信息：修改完子节点后，需要更新当前节点的信息，例如 tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1]。

时间复杂度：O(logN)。同样是每次递归减半，最多访问 logN 层。

区间修改（Range Update）： 将区间 [update_start, update_end] 内的每个元素都加上一个值 delta。

区间修改比单点修改复杂一些，因为如果直接修改所有叶子节点，时间复杂度又回到 O(N)。为了保持 O(logN) 的复杂度，我们需要引入一个叫做**懒惰标记（Lazy Propagation）**的技术。

懒惰标记（Lazy Propagation）

当需要对一个大区间进行修改时，如果当前节点代表的区间完全包含在修改区间内，我们就不再继续向下递归修改其所有子节点，而是在这个节点上打一个“标记”（lazy tag），表示它下面的子节点需要被修改，但是我们暂时不修改它们。这个标记会累加，当之后有查询或者其他修改操作涉及到这个节点的子节点时，我们再把这个标记“下推”到子节点。

每个节点除了存储维护的信息（比如区间和），还需要额外存储一个 lazy 标记。

update(node_idx, current_start, current_end, update_start, update_end, delta)：

  1. 下推懒惰标记：在进行任何操作之前，如果当前节点有懒惰标记，先将其下推到子节点。
    • push_down(node_idx, current_start, current_end)：
      • 如果 lazy[node_idx] 不为0：
        • 更新左右子节点的 tree 值和 lazy 值。
        • 例如：tree[2*node_idx] += lazy[node_idx] * (mid - current_start + 1)
        • lazy[2*node_idx] += lazy[node_idx]
        • tree[2*node_idx+1] += lazy[node_idx] * (current_end - mid)
        • lazy[2*node_idx+1] += lazy[node_idx]
        • 清除当前节点的 lazy[node_idx] = 0。
  2. 完全包含：如果当前节点代表的区间完全包含在修改区间内，直接更新 tree[node_idx] 的值，并给 lazy[node_idx] 加上 delta。然后返回。
  3. 完全不相交：如果完全不相交，直接返回。
  4. 部分相交：
    • 计算 mid = (current_start + current_end) / 2。
    • 递归修改左子树。
    • 递归修改右子树。
    • 更新当前节点信息（合并左右子节点）。

query(node_idx, current_start, current_end, query_start, query_end)：

  1. 下推懒惰标记：在进行任何操作之前，如果当前节点有懒惰标记，先将其下推到子节点。
  2. 完全包含：如果当前节点代表的区间完全包含在查询区间内，直接返回 tree[node_idx] 的值。
  3. 完全不相交：如果完全不相交，返回一个“空值”。
  4. 部分相交：
    • 递归查询左子树。
    • 递归查询右子树。
    • 合并结果返回。

时间复杂度：O(logN)。懒惰标记保证了每个节点最多被访问常数次。

C++ 实现示例（以区间求和为例）

C++

#include <iostream>
#include <vector>

const int MAXN = 100005; // 假设数组最大长度

long long arr[MAXN];    // 原始数组
long long tree[MAXN * 4]; // 线段树存储区间和
long long lazy[MAXN * 4]; // 懒惰标记，存储需要累加的值

// 构建线段树
// node_idx: 当前节点的索引
// current_start, current_end: 当前节点代表的区间范围
void build(int node_idx, int current_start, int current_end) {
    lazy[node_idx] = 0; // 初始化懒惰标记
    if (current_start == current_end) {
        tree[node_idx] = arr[current_start];
    } else {
        int mid = (current_start + current_end) / 2;
        build(2 * node_idx, current_start, mid);
        build(2 * node_idx + 1, mid + 1, current_end);
        tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1];
    }
}

// 下推懒惰标记
// node_idx: 当前节点的索引
// current_start, current_end: 当前节点代表的区间范围
void push_down(int node_idx, int current_start, int current_end) {
    if (lazy[node_idx] != 0 && current_start != current_end) { // 如果有懒惰标记且不是叶子节点
        int mid = (current_start + current_end) / 2;

        // 更新左子节点
        tree[2 * node_idx] += lazy[node_idx] * (mid - current_start + 1);
        lazy[2 * node_idx] += lazy[node_idx];

        // 更新右子节点
        tree[2 * node_idx + 1] += lazy[node_idx] * (current_end - mid);
        lazy[2 * node_idx + 1] += lazy[node_idx];

        lazy[node_idx] = 0; // 清除当前节点的懒惰标记
    }
}

// 区间更新（给区间 [update_start, update_end] 加上 delta）
// node_idx: 当前节点的索引
// current_start, current_end: 当前节点代表的区间范围
// update_start, update_end: 要更新的目标区间
// delta: 累加的值
void update_range(int node_idx, int current_start, int current_end, int update_start, int update_end, long long delta) {
    // 下推懒惰标记
    push_down(node_idx, current_start, current_end);

    // 情况1: 当前区间完全不相交于更新区间
    if (current_start > update_end || current_end < update_start) {
        return;
    }

    // 情况2: 当前区间完全包含于更新区间
    if (update_start <= current_start && current_end <= update_end) {
        tree[node_idx] += delta * (current_end - current_start + 1);
        lazy[node_idx] += delta; // 打上懒惰标记
        return;
    }

    // 情况3: 部分相交，递归处理
    int mid = (current_start + current_end) / 2;
    update_range(2 * node_idx, current_start, mid, update_start, update_end, delta);
    update_range(2 * node_idx + 1, mid + 1, current_end, update_start, update_end, delta);

    // 更新当前节点的值（由子节点合并而来）
    tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1];
}

// 区间查询（查询区间 [query_start, query_end] 的和）
// node_idx: 当前节点的索引
// current_start, current_end: 当前节点代表的区间范围
// query_start, query_end: 要查询的目标区间
long long query_range(int node_idx, int current_start, int current_end, int query_start, int query_end) {
    // 下推懒惰标记
    push_down(node_idx, current_start, current_end);

    // 情况1: 当前区间完全不相交于查询区间
    if (current_start > query_end || current_end < query_start) {
        return 0; // 返回0，因为是求和
    }

    // 情况2: 当前区间完全包含于查询区间
    if (query_start <= current_start && current_end <= query_end) {
        return tree[node_idx];
    }

    // 情况3: 部分相交，递归处理
    int mid = (current_start + current_end) / 2;
    long long p1 = query_range(2 * node_idx, current_start, mid, query_start, query_end);
    long long p2 = query_range(2 * node_idx + 1, mid + 1, current_end, query_start, query_end);

    return p1 + p2;
}

int main() {
    int n; // 原始数组长度
    std::cout << "请输入数组长度 N: ";
    std::cin >> n;

    std::cout << "请输入 " << n << " 个元素: ";
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    build(1, 0, n - 1); // 从根节点1开始构建，区间为 [0, n-1]

    std::cout << "初始数组构建完成。" << std::endl;

    // 示例操作
    std::cout << "查询区间 [0, " << n - 1 << "] 的和: " << query_range(1, 0, n - 1, 0, n - 1) << std::endl;

    int l, r;
    long long delta;
    std::cout << "请输入要更新的区间 [L, R] (0-based) 和增量 delta: ";
    std::cin >> l >> r >> delta;
    update_range(1, 0, n - 1, l, r, delta);
    std::cout << "区间 [" << l << ", " << r << "] 已增加 " << delta << std::endl;

    std::cout << "更新后查询区间 [0, " << n - 1 << "] 的和: " << query_range(1, 0, n - 1, 0, n - 1) << std::endl;

    std::cout << "请输入要查询的区间 [L, R] (0-based): ";
    std::cin >> l >> r;
    std::cout << "区间 [" << l << ", " << r << "] 的和: " << query_range(1, 0, n - 1, l, r) << std::endl;

    return 0;
}

总结与技巧

  1. 分治思想：理解线段树的核心是分治，每个节点负责一个区间，通过左右子节点合并信息。
  2. 数组表示：用数组存储线段树，根节点通常从1开始，方便 2p 和 2p+1 的计算。空间复杂度 4N 是一个安全的上界。
  3. 递归实现：构建、查询、修改都是递归实现，注意递归的基准情况和如何合并子节点信息。
  4. 懒惰标记：理解懒惰标记的原理，它在区间修改时避免了对所有叶子节点的遍历，从而将时间复杂度降到 O(logN)。记住 push_down 的时机：在访问子节点之前，如果当前节点有懒惰标记，就需要下推。
  5. 问题转化：线段树可以解决很多区间问题，例如：
    • 区间和、最大值、最小值
    • 区间异或和、区间GCD
    • 区间覆盖、区间赋值（需要更复杂的懒惰标记）
    • 配合离散化解决坐标范围很大的问题
  6. 调试：线段树的调试可能会比较困难，尤其是懒惰标记。建议画图理解递归过程和标记下推过程。
  7. 熟悉模板：一旦理解了基本原理，就可以尝试记住一个线段树的通用模板，然后根据具体问题修改节点存储的信息和合并/更新逻辑。

给你一些练习题（来自洛谷）

  1. P3374 【模板】线段树 1 (单点修改，区间查询和) - 这是最基础的线段树，不需要懒惰标记。
  2. P3372 【模板】线段树 2 (区间修改，区间查询和) - 包含懒惰标记的经典问题。
  3. P3373 【模板】线段树 3 (区间加法、区间乘法、区间查询和) - 更复杂的懒惰标记，需要处理两种优先级不同的操作。

从最简单的模板开始，一步一步理解，多画图，多调试。你会发现线段树虽然写起来代码量稍微大一些，但它的逻辑是相当清晰和优雅的。

加油，acmer！你一定能掌握线段树的！如果你在学习过程中遇到任何具体问题，随时可以再问我。

例题

例题一：【模板】线段树 1 - 单点修改，区间查询和 (洛谷 P3374)

这是线段树最基础的应用，没有懒惰标记。

题目描述：

给定 N 个数，支持两种操作：

  1. 1 x k：将第 x 个数改为 k。
  2. 2 x y：查询区间 [x,y] 的和。

思路分析：

  • 数据结构：线段树的每个节点存储其代表区间的和。
  • 构建 (build)：
    • 叶子节点：tree[node_idx] = arr[index]。
    • 非叶子节点：tree[node_idx] = tree[2*node_idx] + tree[2*node_idx+1]。
  • 单点修改 (update)：
    • 找到对应的叶子节点（即 current_start == current_end == update_idx）。
    • 更新叶子节点的值。
    • 沿着递归路径回溯，更新所有祖先节点的值（因为子节点改变了，父节点的和也会变）。
  • 区间查询 (query)：
    • 如果当前区间完全包含在查询区间内，直接返回当前节点的值。
    • 如果当前区间与查询区间不相交，返回 0。
    • 如果部分相交，递归查询左右子树，并将结果相加。

代码框架（与之前的构建和查询部分基本一致，只是修改部分是单点修改）：

C++

#include <iostream>
#include <vector>

const int MAXN = 100005;
long long arr[MAXN];    // 原始数组
long long tree[MAXN * 4]; // 线段树存储区间和

// 构建线段树
void build(int node_idx, int current_start, int current_end) {
    if (current_start == current_end) {
        tree[node_idx] = arr[current_start];
    } else {
        int mid = (current_start + current_end) / 2;
        build(2 * node_idx, current_start, mid);
        build(2 * node_idx + 1, mid + 1, current_end);
        tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1];
    }
}

// 单点修改 (将 arr[update_idx] 修改为 new_value)
void update_point(int node_idx, int current_start, int current_end, int update_idx, long long new_value) {
    if (current_start == current_end) { // 找到叶子节点
        tree[node_idx] = new_value;
        return;
    }

    int mid = (current_start + current_end) / 2;
    if (update_idx <= mid) { // 在左子树
        update_point(2 * node_idx, current_start, mid, update_idx, new_value);
    } else { // 在右子树
        update_point(2 * node_idx + 1, mid + 1, current_end, update_idx, new_value);
    }
    // 回溯时更新父节点信息
    tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1];
}

// 区间查询 (查询区间 [query_start, query_end] 的和)
long long query_range(int node_idx, int current_start, int current_end, int query_start, int query_end) {
    // 完全不相交
    if (current_start > query_end || current_end < query_start) {
        return 0;
    }
    // 完全包含
    if (query_start <= current_start && current_end <= query_end) {
        return tree[node_idx];
    }

    // 部分相交，递归查询
    int mid = (current_start + current_end) / 2;
    long long p1 = query_range(2 * node_idx, current_start, mid, query_start, query_end);
    long long p2 = query_range(2 * node_idx + 1, mid + 1, current_end, query_start, query_end);
    return p1 + p2;
}

int main() {
    std::ios_base::sync_with_stdio(false); // 加速IO
    std::cin.tie(NULL);

    int n, m; // n: 数组长度, m: 操作次数
    std::cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    build(1, 0, n - 1); // 0-based index for original array

    for (int i = 0; i < m; ++i) {
        int op_type;
        std::cin >> op_type;
        if (op_type == 1) {
            int x; // 注意题目通常是1-based，需要转换为0-based
            long long k;
            std::cin >> x >> k;
            update_point(1, 0, n - 1, x - 1, k); // 转换为0-based
        } else {
            int x, y; // 注意题目通常是1-based，需要转换为0-based
            std::cin >> x >> y;
            std::cout << query_range(1, 0, n - 1, x - 1, y - 1) << "\n"; // 转换为0-based
        }
    }
    return 0;
}

要点：

  • 这道题很简单，关键在于理解线段树的递归结构和父子关系。
  • 单点修改时，只影响一条从叶子节点到根节点的路径上的节点，所以只需要更新这些节点即可。

例题二：【模板】线段树 2 - 区间修改，区间查询和 (洛谷 P3372)

这道题引入了懒惰标记。

题目描述：

给定 N 个数，支持两种操作：

  1. 1 x y k：将区间 [x,y] 内的每个数都加上 k。
  2. 2 x y：查询区间 [x,y] 的和。

思路分析：

  • 数据结构：
    • tree[node_idx]：存储当前节点代表区间的和。
    • lazy[node_idx]：存储当前节点待下推的累加值。
  • 懒惰标记的原理：
    • 当我们对一个区间 [L, R] 进行区间修改时，如果某个节点 u 的区间 [current_start, current_end] 完全包含了 [L, R]，我们直接更新 tree[u] 的值，并在 lazy[u] 上累加修改值。我们不再继续向下递归修改其子节点。
    • 这样，当之后有查询或修改操作需要访问 u 的子节点时，我们必须先调用 push_down 函数，将 u 上的 lazy 标记下推到其子节点。
  • push_down 函数：
    • 判断 lazy[node_idx] 是否为 0。不为 0 才需要下推。
    • 更新左子节点：tree[2*node_idx] += lazy[node_idx] * (左子节点区间长度)
    • 更新左子节点懒惰标记：lazy[2*node_idx] += lazy[node_idx]
    • 更新右子节点（同理）。
    • 清空当前节点的懒惰标记：lazy[node_idx] = 0。
    • 注意：push_down 应该在任何访问子节点（无论是查询还是修改）之前执行。
  • 区间修改 (update_range)：
    • 首先 push_down 当前节点的懒惰标记。
    • 如果当前区间完全不相交于更新区间，直接返回。
    • 如果当前区间完全包含于更新区间：
      • 更新 tree[node_idx]。
      • 更新 lazy[node_idx]。
      • 返回。
    • 如果部分相交：
      • 递归调用左右子树进行修改。
      • 回溯时更新 tree[node_idx]（由新的子节点和合并而来）。
  • 区间查询 (query_range)：
    • 首先 push_down 当前节点的懒惰标记。
    • 如果当前区间完全不相交于查询区间，返回 0。
    • 如果当前区间完全包含于查询区间，返回 tree[node_idx]。
    • 如果部分相交，递归查询左右子树，并将结果相加。

代码框架（这就是我上一个回答中给出的代码示例）：

C++

#include <iostream>
#include <vector>

const int MAXN = 100005; // 假设数组最大长度

long long arr[MAXN];    // 原始数组
long long tree[MAXN * 4]; // 线段树存储区间和
long long lazy[MAXN * 4]; // 懒惰标记，存储需要累加的值

// 构建线段树
void build(int node_idx, int current_start, int current_end) {
    lazy[node_idx] = 0; // 初始化懒惰标记
    if (current_start == current_end) {
        tree[node_idx] = arr[current_start];
    } else {
        int mid = (current_start + current_end) / 2;
        build(2 * node_idx, current_start, mid);
        build(2 * node_idx + 1, mid + 1, current_end);
        tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1];
    }
}

// 下推懒惰标记
void push_down(int node_idx, int current_start, int current_end) {
    if (lazy[node_idx] != 0 && current_start != current_end) { // 如果有懒惰标记且不是叶子节点
        int mid = (current_start + current_end) / 2;

        // 更新左子节点
        tree[2 * node_idx] += lazy[node_idx] * (mid - current_start + 1);
        lazy[2 * node_idx] += lazy[node_idx];

        // 更新右子节点
        tree[2 * node_idx + 1] += lazy[node_idx] * (current_end - mid);
        lazy[2 * node_idx + 1] += lazy[node_idx];

        lazy[node_idx] = 0; // 清除当前节点的懒惰标记
    }
}

// 区间更新（给区间 [update_start, update_end] 加上 delta）
void update_range(int node_idx, int current_start, int current_end, int update_start, int update_end, long long delta) {
    // 下推懒惰标记
    push_down(node_idx, current_start, current_end);

    // 情况1: 当前区间完全不相交于更新区间
    if (current_start > update_end || current_end < update_start) {
        return;
    }

    // 情况2: 当前区间完全包含于更新区间
    if (update_start <= current_start && current_end <= update_end) {
        tree[node_idx] += delta * (current_end - current_start + 1);
        lazy[node_idx] += delta; // 打上懒惰标记
        return;
    }

    // 情况3: 部分相交，递归处理
    int mid = (current_start + current_end) / 2;
    update_range(2 * node_idx, current_start, mid, update_start, update_end, delta);
    update_range(2 * node_idx + 1, mid + 1, current_end, update_start, update_end, delta);

    // 更新当前节点的值（由子节点合并而来）
    tree[node_idx] = tree[2 * node_idx] + tree[2 * node_idx + 1];
}

// 区间查询（查询区间 [query_start, query_end] 的和）
long long query_range(int node_idx, int current_start, int current_end, int query_start, int query_end) {
    // 下推懒惰标记
    push_down(node_idx, current_start, current_end);

    // 情况1: 当前区间完全不相交于查询区间
    if (current_start > query_end || current_end < query_start) {
        return 0; // 返回0，因为是求和
    }

    // 情况2: 当前区间完全包含于查询区间
    if (query_start <= current_start && current_end <= query_end) {
        return tree[node_idx];
    }

    // 情况3: 部分相交，递归处理
    int mid = (current_start + current_end) / 2;
    long long p1 = query_range(2 * node_idx, current_start, mid, query_start, query_end);
    long long p2 = query_range(2 * node_idx + 1, mid + 1, current_end, query_start, query_end);

    return p1 + p2;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    build(1, 0, n - 1); // 0-based index

    for (int i = 0; i < m; ++i) {
        int op_type;
        std::cin >> op_type;
        if (op_type == 1) {
            int x, y;
            long long k;
            std::cin >> x >> y >> k;
            update_range(1, 0, n - 1, x - 1, y - 1, k);
        } else {
            int x, y;
            std::cin >> x >> y;
            std::cout << query_range(1, 0, n - 1, x - 1, y - 1) << "\n";
        }
    }
    return 0;
}

要点：

  • 理解 push_down 的必要性，它确保了在访问子节点时，子节点的值是最新的。
  • 懒惰标记的值是累加的，因为可能多次对同一个区间进行修改。
  • 下推时，懒惰标记的值需要乘上子区间长度，因为 lazy 标记存储的是每个元素要增加的值，而不是区间总和要增加的值。
  • lazy[node_idx] = 0 在下推后必须清除，否则会重复下推。

例题三：【模板】线段树 3 - 区间加法、区间乘法、区间查询和 (洛谷 P3373)

这道题是线段树的进阶，需要处理两种优先级不同的懒惰标记：加法和乘法。

题目描述：

给定 N 个数和 P，支持三种操作：

  1. 1 x y k：将区间 [x,y] 内的每个数都乘以 k。
  2. 2 x y k：将区间 [x,y] 内的每个数都加上 k。
  3. 3 x y：查询区间 [x,y] 的和，对 P 取模。

思路分析：

  • 难点：同时有加法和乘法标记时，它们的顺序会影响结果。例如，(a + b) * c 不等于 a * c + b。通常遵循先乘后加的原则。

  • 数据结构：

    • tree[node_idx]：存储区间和。
    • mul_lazy[node_idx]：乘法懒惰标记，初始为 1。
    • add_lazy[node_idx]：加法懒惰标记，初始为 0。

  • push_down 函数：

    • 处理顺序：先乘后加。
    • 如果 mul_lazy[node_idx] != 1 或 add_lazy[node_idx] != 0：
      1. 下推乘法标记：
        • 更新左子节点：tree[2*node_idx] = (tree[2*node_idx] * mul_lazy[node_idx]) % P
        • 更新左子节点懒惰标记：
          • mul_lazy[2*node_idx] = (mul_lazy[2*node_idx] * mul_lazy[node_idx]) % P
          • add_lazy[2*node_idx] = (add_lazy[2*node_idx] * mul_lazy[node_idx]) % P
        • 右子节点同理。
      2. 下推加法标记：
        • 更新左子节点：tree[2*node_idx] = (tree[2*node_idx] + add_lazy[node_idx] * (左子节点区间长度)) % P
        • 更新左子节点懒惰标记：add_lazy[2*node_idx] = (add_lazy[2*node_idx] + add_lazy[node_idx]) % P
        • 右子节点同理。
      3. 清除当前节点标记：mul_lazy[node_idx] = 1; add_lazy[node_idx] = 0;

  • update_multiply (区间乘法)：

    • push_down。
    • 如果完全包含：
      • tree[node_idx] = (tree[node_idx] * k) % P
      • mul_lazy[node_idx] = (mul_lazy[node_idx] * k) % P
      • add_lazy[node_idx] = (add_lazy[node_idx] * k) % P (这里的 add_lazy 也需要乘以 k，因为以后下推时，它代表的加法值也需要被 k 放大)
    • 否则递归，回溯时更新 tree[node_idx]。

  • update_add (区间加法)：

    • push_down。
    • 如果完全包含：
      • tree[node_idx] = (tree[node_idx] + k * (区间长度)) % P
      • add_lazy[node_idx] = (add_lazy[node_idx] + k) % P
    • 否则递归，回溯时更新 tree[node_idx]。

  • query_range (区间查询)：

    • push_down。
    • 返回逻辑和之前一样。

代码框架（只展示关键部分，具体实现需要仔细）：

C++

#include <iostream>
#include <vector>

const int MAXN = 100005;
long long arr[MAXN];
long long tree[MAXN * 4];
long long mul_lazy[MAXN * 4]; // 乘法懒惰标记
long long add_lazy[MAXN * 4]; // 加法懒惰标记
long long MOD; // 取模的值 P

// 辅助函数：计算区间长度
long long get_len(int current_start, int current_end) {
    return current_end - current_start + 1;
}

// 构建线段树
void build(int node_idx, int current_start, int current_end) {
    mul_lazy[node_idx] = 1; // 乘法标记初始化为1
    add_lazy[node_idx] = 0; // 加法标记初始化为0
    if (current_start == current_end) {
        tree[node_idx] = arr[current_start] % MOD; // 初始化时也要取模
    } else {
        int mid = (current_start + current_end) / 2;
        build(2 * node_idx, current_start, mid);
        build(2 * node_idx + 1, mid + 1, current_end);
        tree[node_idx] = (tree[2 * node_idx] + tree[2 * node_idx + 1]) % MOD;
    }
}

// 下推懒惰标记
void push_down(int node_idx, int current_start, int current_end) {
    if (mul_lazy[node_idx] == 1 && add_lazy[node_idx] == 0) { // 没有懒惰标记，直接返回
        return;
    }

    // 不是叶子节点才能下推
    if (current_start == current_end) {
        // 叶子节点不向下推，直接更新它自己的值
        // 但其实这里可以不用处理，因为叶子节点不会有子节点可以下推
        // 如果是叶子节点，懒惰标记就相当于已经作用在它自己身上了
        return;
    }

    int mid = (current_start + current_end) / 2;
    long long left_child_len = get_len(current_start, mid);
    long long right_child_len = get_len(mid + 1, current_end);

    // 1. 下推乘法标记 (先乘)
    // 更新左子节点
    tree[2 * node_idx] = (tree[2 * node_idx] * mul_lazy[node_idx]) % MOD;
    mul_lazy[2 * node_idx] = (mul_lazy[2 * node_idx] * mul_lazy[node_idx]) % MOD;
    add_lazy[2 * node_idx] = (add_lazy[2 * node_idx] * mul_lazy[node_idx]) % MOD; // 重要的！加法标记也要乘以乘法标记

    // 更新右子节点
    tree[2 * node_idx + 1] = (tree[2 * node_idx + 1] * mul_lazy[node_idx]) % MOD;
    mul_lazy[2 * node_idx + 1] = (mul_lazy[2 * node_idx + 1] * mul_lazy[node_idx]) % MOD;
    add_lazy[2 * node_idx + 1] = (add_lazy[2 * node_idx + 1] * mul_lazy[node_idx]) % MOD;

    // 2. 下推加法标记 (后加)
    // 更新左子节点
    tree[2 * node_idx] = (tree[2 * node_idx] + add_lazy[node_idx] * left_child_len) % MOD;
    add_lazy[2 * node_idx] = (add_lazy[2 * node_idx] + add_lazy[node_idx]) % MOD;

    // 更新右子节点
    tree[2 * node_idx + 1] = (tree[2 * node_idx + 1] + add_lazy[node_idx] * right_child_len) % MOD;
    add_lazy[2 * node_idx + 1] = (add_lazy[2 * node_idx + 1] + add_lazy[node_idx]) % MOD;

    // 清除当前节点标记
    mul_lazy[node_idx] = 1;
    add_lazy[node_idx] = 0;
}


// 区间乘法
void update_multiply(int node_idx, int current_start, int current_end, int update_start, int update_end, long long k) {
    push_down(node_idx, current_start, current_end); // 先下推

    if (current_start > update_end || current_end < update_start) {
        return;
    }

    if (update_start <= current_start && current_end <= update_end) {
        tree[node_idx] = (tree[node_idx] * k) % MOD;
        mul_lazy[node_idx] = (mul_lazy[node_idx] * k) % MOD;
        add_lazy[node_idx] = (add_lazy[node_idx] * k) % MOD; // 加法标记也需要乘以 k
        return;
    }

    int mid = (current_start + current_end) / 2;
    update_multiply(2 * node_idx, current_start, mid, update_start, update_end, k);
    update_multiply(2 * node_idx + 1, mid + 1, current_end, update_start, update_end, k);

    tree[node_idx] = (tree[2 * node_idx] + tree[2 * node_idx + 1]) % MOD;
}

// 区间加法
void update_add(int node_idx, int current_start, int current_end, int update_start, int update_end, long long k) {
    push_down(node_idx, current_start, current_end); // 先下推

    if (current_start > update_end || current_end < update_start) {
        return;
    }

    if (update_start <= current_start && current_end <= update_end) {
        tree[node_idx] = (tree[node_idx] + k * get_len(current_start, current_end)) % MOD;
        add_lazy[node_idx] = (add_lazy[node_idx] + k) % MOD;
        return;
    }

    int mid = (current_start + current_end) / 2;
    update_add(2 * node_idx, current_start, mid, update_start, update_end, k);
    update_add(2 * node_idx + 1, mid + 1, current_end, update_start, update_end, k);

    tree[node_idx] = (tree[2 * node_idx] + tree[2 * node_idx + 1]) % MOD;
}


// 区间查询
long long query_range(int node_idx, int current_start, int current_end, int query_start, int query_end) {
    push_down(node_idx, current_start, current_end); // 先下推

    if (current_start > query_end || current_end < query_start) {
        return 0;
    }

    if (query_start <= current_start && current_end <= query_end) {
        return tree[node_idx];
    }

    int mid = (current_start + current_end) / 2;
    long long p1 = query_range(2 * node_idx, current_start, mid, query_start, query_end);
    long long p2 = query_range(2 * node_idx + 1, mid + 1, current_end, query_start, query_end);

    return (p1 + p2) % MOD;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m >> MOD; // 额外输入 MOD

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    build(1, 0, n - 1); // 0-based index

    for (int i = 0; i < m; ++i) {
        int op_type;
        std::cin >> op_type;
        int x, y;
        long long k;
        if (op_type == 1) { // 乘法
            std::cin >> x >> y >> k;
            update_multiply(1, 0, n - 1, x - 1, y - 1, k);
        } else if (op_type == 2) { // 加法
            std::cin >> x >> y >> k;
            update_add(1, 0, n - 1, x - 1, y - 1, k);
        } else { // 查询
            std::cin >> x >> y;
            std::cout << query_range(1, 0, n - 1, x - 1, y - 1) << "\n";
        }
    }
    return 0;
}

要点：

  • 懒惰标记的优先级：乘法优先于加法。在 push_down 时，总是先处理乘法标记，再处理加法标记。
  • 加法标记的更新：当有乘法操作 *k 时，节点上的加法标记 add_lazy 也需要乘以 k。因为如果之前有 +A 的操作，现在整个区间乘以 k，那么原本 +A 的效果就变成了 +A*k。
  • 取模：题目要求对 P 取模，所有涉及到求和、乘法的地方都要进行 % MOD 操作，防止溢出。尤其注意负数取模的问题（C++ 中 % 负数可能得到负数，需要 (X % MOD + MOD) % MOD 来保证非负）。这里假设都是正数。
  • push_down 的判断：只有当 mul_lazy 不为1或者 add_lazy 不为0时才需要下推。

总结与提高

通过这三个例题，你应该对线段树的构建、单点修改、区间修改（带懒惰标记）、区间查询有了更深入的理解。

更深入的思考：

  1. 线段树的应用不限于求和：
    • 区间最大/最小值：节点存储最大/最小值，合并时取 max(left_child, right_child)。懒惰标记可能更复杂，例如区间赋值（assign）操作。
    • 区间异或和：合并时取 left_child ^ right_child。
    • 区间 GCD：合并时取 gcd(left_child, right_child)。
    • 统计某种性质的数量：例如区间内有多少个奇数/偶数。
  2. 动态开点线段树：如果区间的范围非常大（例如 109），但实际需要操作的点的数量相对较少，普通的线段树会占用太多空间。这时可以使用动态开点线段树，只有在需要时才创建节点。
  3. 线段树套线段树：处理二维或多维问题，例如查询一个矩形区域内的和。
  4. 扫描线：线段树结合扫描线技术可以解决矩形面积并、周长并等几何问题。

给你的建议：

  • 从简单开始：先彻底理解单点修改和区间查询。
  • 再攻克懒惰标记：这是线段树的难点，需要反复推敲 push_down 的逻辑。可以尝试在纸上模拟 push_down 的过程，看看标记是如何传递和更新的。
  • 多写多练：刷题是最好的学习方式。尝试洛谷上的线段树模板题，以及其他相关题目。
  • 画图辅助理解：当遇到复杂逻辑时，画出线段树的结构图，标出节点和区间，能帮助你理清思路。

线段树是一个非常强大的工具，掌握它之后，你会发现很多看起来复杂的区间问题变得迎刃而解。加油！

推荐文章

1
Problems
8008: 纸牌游戏（ "Accordian" Patience）
2
SystemConfig
Arch 休眠总失败？Swap 分区配置一次到位
3
Git
子仓库怎么塞进父仓库：Submodule 与 Subtree 对比
4
DP
分组背包变式：每组恰好选 $d_i$ 件
5
Backend
Spring 循环依赖怎么解决？

相关文章

1
DataStructure
线段树模板
2
Prefix
树上差分
3
Graph
并查集常见变式
4
Graph
图论中的基本概念
5
Graph
树链剖分模板