當前沒有測試資料。

线段树

一、引入（前言）

给定一个长度为 $N$ 的整数序列 $a_1, a_2, \dots, a_N$。需要处理 $Q$ 个操作，操作分为两种：

• 1 p x：将位置 $p$ 上的数修改为 $x$（单点修改）。
• 2 l r：查询区间 $[l, r]$ 内所有数的和（区间查询）。

$N, Q \le 2 \times 10^5$。

先看手头的工具：

• 前缀和：预处理 $O(N)$，区间查询 $O(1)$。但修改一个元素后，从该位置到末尾的前缀和全部失效，必须重建，单次修改 $O(N)$。修改和查询穿插时，总复杂度退化为 $O(QN)$。
• 暴力：修改直接改数组 $O(1)$，查询时从 $l$ 遍历到 $r$，$O(N)$。同样 $O(QN)$，不可行。

又一次遇到了当年前缀和和差分打架时的老问题——修改和查询无法两全。今天我们要追求比 $O(N)$ 更高的效率——$O(\log N)$。

回忆一下，之前学归并排序时用过一个策略：把数组不断对半拆分，分别排序两半，再合并。这个"对半拆分 + 分别处理 + 合并结果"的模式，在算法竞赛中有个专门的名称——分治。

现在换一个角度看待归并排序的拆分过程。我们不关心"如何排序"，而是关心"拆分后每一段的信息"。归并排序的递归把原数组拆成了这样一棵树：

                      [1, 8]
                     /      \
              [1, 4]          [5, 8]
             /     \          /     \
        [1, 2]   [3, 4]  [5, 6]   [7, 8]
        /    \   /    \  /    \   /    \
      [1]  [2] [3]  [4] [5] [6] [7]  [8]

如果在每个节点上不排序、而是存这段区间的总和，会怎样？

• 查询 $[2, 6]$ 的和时，不需要遍历 $5$ 个元素。$[3,4]$ 和 $[5,6]$ 这两段是被完全覆盖的，直接从树上取它们的预存总和即可。只需要再暴力处理边缘的 $[2]$ 和 $[7]$。
• 修改位置 $3$ 时，只需更新包含 $3$ 的那些节点：$[3] \to [3,4] \to [1,4] \to [1,8]$，一路向根更新，恰好 $O(\log N)$。

这就是线段树——把归并排序的"分治拆分"拿过来，在每个节点上存一段区间的聚合信息（如求和、最大值、最小值），从而在 $O(\log N)$ 内完成单点修改和区间查询。

---

二、算法思路与核心逻辑

2.1 问题拆解

本题的核心矛盾是：修改需要触及单个元素，查询需要覆盖大量元素。一种理想的数据结构应当能够同时做到：

• 查询快：对于任意区间 $[l, r]$，能快速获取答案，而不是逐元素遍历。
• 修改快：单个元素修改后，能快速更新受影响的信息，而不是全盘重建。

问题的本质是信息组织——如何把 $N$ 个元素组织起来，使得"合并一段连续元素的信息"和"更新单个元素"的代价都足够小。

回顾我们见过的策略：

• 线性组织（前缀和）：元素按顺序排列，预计算前缀信息。查询时用"两端相减"快速得到任意区间，但修改时"牵一发而动全身"。
• 树形组织：如果把元素放在叶子节点，中间节点存储子节点的合并信息，查询时走到合适的节点直接取值，修改时只走一条从叶到根的路径。这正是归并排序拆分策略给我们的启发。

观察到：归并排序的拆分树中，每个节点恰好对应原数组的一个连续区间，而且这棵树是平衡的（每次都尽量对半分）。这意味着从根到任意叶子的长度是 $O(\log N)$，任意区间可以被拆分成 $O(\log N)$ 个树上节点的并。

关键洞察：如果把"对半拆分 + 分别预存信息"的策略从排序场景移植到区间操作场景，就能得到一棵"每个节点存区间信息、修改沿路径更新、查询按覆盖节点取用"的数据结构——线段树。

2.2 算法诞生

第一步：从归并排序的拆分树出发

归并排序的递归过程，本质上是对数组下标区间做了一次二叉树剖分。给定区间 $[l, r]$：

• 若 $l = r$，这是单个元素，不再拆分（叶子节点）。
• 否则，令 $\textit{mid} = \lfloor(l + r) / 2\rfloor$，拆成左半 $[l, \textit{mid}]$ 和右半 $[\textit{mid}+1, r]$，分别递归。

这个过程产生了一棵二叉树。以 $N = 5$ 为例：

                    [1, 5]
                   /      \
            [1, 3]          [4, 5]
           /     \          /     \
      [1, 2]    [3, 3]  [4, 4]  [5, 5]
      /    \
  [1, 1]  [2, 2]

这棵树有 $N$ 个叶子节点（每个位置恰好一个），内部节点数不超过 $N-1$，总节点数不超过 $2N$。树的高度约为 $\lceil\log_2 N\rceil$，因此从根到任意叶子的路径长度是 $O(\log N)$。

第二步：在节点上存信息

现在不再在每个节点做"排序"，而是存这个节点对应区间的聚合信息。以区间求和为例：

• 叶子节点 $[p, p]$：存储 $a_p$ 本身。
• 内部节点 $[l, r]$：存储 $\textit{sum} = \text{左孩子.sum} + \text{右孩子.sum}$。

于是从叶子到根，逐层往上合并，整棵树就完成了构建。这个构建过程和归并排序的"合并"步骤逻辑一致——归并排序中每个节点合并两个有序列表，而线段树中每个节点合并两个子区间的信息。

建树完成后，根节点 $[1, N]$ 存储的就是整个数组的总和。

第三步：区间查询

查询区间 $[\textit{ql}, \textit{qr}]$ 的和时，从根节点开始递归。对于当前节点 $[l, r]$：

• 完全覆盖：若 $\textit{ql} \le l$ 且 $r \le \textit{qr}$（查询区间完全包含当前节点），则当前节点的 $\textit{sum}$ 就是这部分的和，直接返回，不需要再递归下去。
• 完全不交：若 $\textit{qr} < l$ 或 $\textit{ql} > r$（查询区间与当前节点没有交集），返回 $0$。
• 部分相交：否则，查询区间和当前节点有交集但不完全覆盖。递归进入左孩子和右孩子，分别获取结果，再求和返回。

查询 [2, 5] 的过程（N = 5，用上图的树）：

                    [1, 5]          <- 部分相交，需要左右分头查
                   /      \
            [1, 3]          [4, 5]  <- [4,5] 被 [2,5] 完全覆盖！直接返回 sum
           /     \          
      [1, 2]    [3, 3]              <- [3,3] 被完全覆盖！直接返回 sum
      /    \
  [1, 1]  [2, 2]                    <- [2,2] 被完全覆盖！直接返回 sum

结果 = sum[2,2] + sum[3,3] + sum[4,5]，只访问了 O(log N) 个节点。

查询过程中，每一层最多只会展开 $2$ 个"部分相交"的节点（因为区间是连续的，与一条竖线相交的区间最多只有 $2$ 个），其余节点要么被完全覆盖（直接返回），要么完全不交（剪枝）。树高 $O(\log N)$，因此总访问节点数为 $O(\log N)$。

第四步：单点修改

修改位置 $p$ 时，从根向下找到叶子 $[p, p]$，更新它的值。然后沿递归路径逐层回溯，用更新后的左右孩子重新计算当前节点的值。

修改 a[2] 后，需要更新的节点：
  [2,2] -> [1,2] -> [1,3] -> [1,5]

恰好是根到叶子的路径，O(log N) 个节点。

注意，实现时递归函数在修改叶子后返回，返回时自然会经过路径上的所有祖先，顺手更新即可。

第五步：区间修改——懒标记

如果题目变成区间加（1 l r x：将 $[l, r]$ 内所有数加上 $x$），再用上面逐个修改叶子的方式，最坏 $O(N \log N)$，退化了。

解决方案是懒标记（Lazy Tag）：

• 在线段树的每个节点上额外维护一个 $\textit{lazy}$ 值，表示"这个节点对应的区间曾经被整体加上了多少，但还没有下发给孩子"。
• 当一次区间加完全覆盖某节点时，更新该节点的 $\textit{sum}$（加上 $x \times \text{区间长度}$），并在 $\textit{lazy}$ 上累加 $x$，然后不再向下递归。
• 当后续操作需要访问该节点的孩子时（查询或修改进入了范围更细的区间），才把 $\textit{lazy}$ 下推给孩子：将懒标记传给左右孩子，更新它们的 $\textit{sum}$ 和 $\textit{lazy}$，然后清空自己的懒标记。

懒标记的思想本质上是延迟计算——"反正这个区间整个都要加，我先记着，等有人需要更细的信息时再往下传"。有了懒标记，区间修改同样是 $O(\log N)$。

一句话总结：线段树 = 归并排序的分治拆分树 + 节点存储区间聚合信息 + 查询时取完全覆盖的节点 + 修改时沿路径更新 + 懒标记延迟下发。单次操作 $O(\log N)$。

2.3 算法特征与关键细节

核心特征

特征	说明
树结构	一棵平衡的二叉树。每个节点对应数组的一个区间 $[l, r]$，叶子对应单个元素。
节点信息	存储该区间的聚合值（$\textit{sum}$ / $\textit{max}$ / $\textit{min}$ 等），以及可选的懒标记 $\textit{lazy}$。
构建方式	自顶向下递归拆分区间，自底向上合并子节点信息。与归并排序的拆分和合并过程同构。
查询方式	从根递归，遇完全覆盖则直接返回，遇不交则剪枝，遇部分交则分裂进入子树。
修改方式	单点：沿路径更新。区间：覆盖时打懒标记停止递归，进入子节点时先下推懒标记。
节点数量	不超过 $4N$，通常开 MAXN * 4 的数组确保安全。
算法类型	基于分治的树形数据结构，支持区间信息的快速维护。

与树状数组、ST 表的对比

线段树不是孤立存在的。在学习它之前，其实我们基本都学过树状数组和ST 表。它们三个都是处理区间问题的工具，但各有各的主场。下表从多个维度给出对比：

维度	线段树	树状数组	ST 表
单点修改	$O(\log N)$		不支持
区间修改	$O(\log N)$（懒标记）	$O(\log N)$（需配合差分）
区间查询	$O(\log N)$		$O(1)$
支持的区间操作（举例）	求和、最大值、最小值、GCD、LCM、异或和、矩阵乘积……（几乎一切满足结合律的运算）	求和、异或和（只能处理有逆运算的操作：大区间信息减去左半边等于右半边）	最大值、最小值、GCD、LCM（只能处理可重复贡献的操作：一个元素可以重复参与运算不改变结果）
能否处理修改	可在线修改		纯静态，建表后数组不能变
空间占用	$4N$	$N$	$N \log N$
代码量	$\sim 50$ 行	$\sim 15$ 行	$\sim 10$ 行

这张表揭示了三个数据结构各自的定位：

• ST 表的绝活是 $O(1)$ 查询——在"数组不变、只查最值"的场景下（如多次询问区间最大值），ST 表是最优解，没有任何数据结构能在查询速度上超越它。但它完全不能处理修改，数组一旦改变就必须重建。
• 树状数组是线段树的"轻量级替代"。代码极短、常数极小、空间只要 $N$。但它的致命弱点是只能处理有逆运算的操作——求和、异或这类"大区间减去左半边等于右半边"的运算。如果你要求区间最大值，树状数组就无能为力了，因为 $\max[1, r]$ 减去 $\max[1, l-1]$ 什么也不是。
• 线段树是三者中功能最全面的：既能处理修改，又能处理最大值/GCD 这类没有逆运算的信息。代价是代码最长、常数最大、空间最大。可以把线段树理解为"什么都能干，但不一定是最优的那个"——如果树状数组够用，树状数组更快更短；如果 ST 表够用，ST 表查询秒杀一切。

选型口诀：数组不变只查最值用 ST 表，只做求和/异或的修改+查询用树状数组，其余一切区间问题找线段树。

相关概念

概念	定义	与线段树的关系
主席树（可持久化线段树）	在线段树基础上保留每次修改的历史版本，形成多棵共享节点的线段树。	是线段树的"可持久化"扩展，用于处理"查询历史版本"的问题。
线段树合并	将两棵线段树的对应节点合并，常用在树上统计问题中。	利用线段树的递归结构，在 $O(\text{相同节点数})$ 的时间内合并两棵树。
动态开点线段树	不在一开始建满整棵树，而是需要时才创建节点，适用于下标范围很大但实际访问很少的场景。	用指针或数组模拟按需分配节点，取代固定 $4N$ 的预分配。

关键实现细节

细节	说明
数组大小	通常开 $\textit{MAXN} \times 4$。理论最坏情况需要 $4N - 1$ 个节点（$N$ 为 $2$ 的幂时约 $2N$，非幂次时最坏约 $4N$）。
节点编号	普遍采用堆式存储：根节点编号为 $1$，左孩子为 $2k$，右孩子为 $2k+1$。不显式存左右指针。
mid 的计算	$\textit{mid} = (l + r) / 2$ 在整数除法下自动向下取整，左区间 $[l, \textit{mid}]$、右区间 $[\textit{mid}+1, r]$。注意避免 l + r 溢出（C++ 中 $N \le 2\times10^5$ 时不会溢出，但养成用 l + (r - l) / 2 的习惯有益无害）。
空节点处理	查询时"完全不交"返回单位元：求和返回 $0$，求最大值返回 $-\infty$，求最小值返回 $+\infty$。这个返回值必须不干扰最终结果。
懒标记下推（pushdown）	每次进入孩子节点前必须先 pushdown(k, l, r)，将当前节点的 $\textit{lazy}$ 传给左右孩子并更新孩子的 $\textit{sum}$，然后清空自己的 $\textit{lazy}$。否则孩子的信息是"过时"的。
更新后合并（pushup）	每次递归返回前（孩子信息可能被修改后），必须用左右孩子的最新值重新计算当前节点的值：$\textit{tree}[k] = \textit{tree}[2k] + \textit{tree}[2k+1]$。
build / query / update 的参数设计	三个函数统一接受 $(k, l, r, \dots)$ 参数：$k$ 是节点编号，$l, r$ 是该节点对应的区间。这样递归时不需要额外计算区间，直接传入即可。

---

三、时间复杂度分析

阶段	复杂度	说明
建树	$O(N)$	每个节点恰好被访问一次，共不超过 $4N$ 个节点。每个节点做 $O(1)$ 的合并操作。
单点修改	$O(\log N)$	从根到目标叶子的路径长度 $= O(\log N)$，路径上每个节点更新一次。
区间查询		每层至多展开 $4$ 个节点（两个"部分相交"各展开左右孩子），树高 $O(\log N)$，访问节点数 $O(\log N)$。
区间修改（带懒标记）		与区间查询相同的访问模式，覆盖节点时打标记停止，不覆盖时递归进入子节点。
总复杂度	$O(N + Q \log N)$	对 $N, Q \le 2 \times 10^5$ 完全可行。

---

四、模板题与模板代码

题目描述（简版）

给定一个长度为 $N$ 的序列 $a_1, a_2, \dots, a_N$。处理 $Q$ 个操作：

• 1 l r x：将区间 $[l, r]$ 内的所有数加上 $x$。
• 2 l r：查询区间 $[l, r]$ 内所有数的和。

数据范围：$1 \le N, Q \le 2 \times 10^5$，$|a_i|, |x| \le 10^4$。答案可能超过 $2^{31}$，使用 long long。

样例

输入：
5 5
1 2 3 2 1
2 1 5
1 2 4 2
2 1 5
1 1 3 1
2 2 4

输出：
9
15
12

模板代码

#include <iostream>
using namespace std;
typedef long long ll;

const int MAXN = 200005;

int n, q;
ll a[MAXN];                          // 原始数组

// ---------- 线段树 ----------
ll tree[MAXN * 4];                   // 节点存储区间和
ll lazy[MAXN * 4];                   // 懒标记

// 构建线段树：k = 当前节点编号, [l, r] = 当前节点对应的区间
void build(int k, int l, int r) {
    if (l == r) {
        tree[k] = a[l];              // 叶子节点 = 数组元素本身
        return;
    }
    int mid = (l + r) / 2;
    build(k * 2, l, mid);            // 递归建左子树
    build(k * 2 + 1, mid + 1, r);    // 递归建右子树
    tree[k] = tree[k * 2] + tree[k * 2 + 1];   // 合并左右子树的信息
}

// 下推懒标记：将当前节点的懒标记传给两个孩子
void pushdown(int k, int l, int r) {
    if (lazy[k] == 0) return;        // 没有标记，无需下推
    int mid = (l + r) / 2;
    int left = k * 2, right = k * 2 + 1;

    // 传给左孩子
    tree[left] += lazy[k] * (mid - l + 1);
    lazy[left] += lazy[k];
    // 传给右孩子
    tree[right] += lazy[k] * (r - mid);
    lazy[right] += lazy[k];
    // 清空当前节点的懒标记
    lazy[k] = 0;
}

// 区间加：[ql, qr] 整体加上 x
void rangeAdd(int k, int l, int r, int ql, int qr, ll x) {
    if (ql <= l && r <= qr) {        // 当前区间被完全覆盖
        tree[k] += x * (r - l + 1);   // 更新总和
        lazy[k] += x;                 // 打上懒标记
        return;
    }
    pushdown(k, l, r);               // 进入孩子前先下推懒标记
    int mid = (l + r) / 2;
    if (ql <= mid) rangeAdd(k * 2, l, mid, ql, qr, x);
    if (qr > mid)  rangeAdd(k * 2 + 1, mid + 1, r, ql, qr, x);
    tree[k] = tree[k * 2] + tree[k * 2 + 1];   // 用更新后的孩子重新计算当前节点
}

// 区间查询：[ql, qr] 的和
ll rangeQuery(int k, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {        // 当前区间被完全覆盖
        return tree[k];
    }
    pushdown(k, l, r);               // 进入孩子前先下推懒标记
    int mid = (l + r) / 2;
    ll res = 0;
    if (ql <= mid) res += rangeQuery(k * 2, l, mid, ql, qr);
    if (qr > mid)  res += rangeQuery(k * 2 + 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 1. 建树：从根节点 1 开始，管理区间 [1, n]
    build(1, 1, n);

    // 2. 处理操作
    while (q--) {
        int op, l, r;
        ll x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            rangeAdd(1, 1, n, l, r, x);
        } else {
            cout << rangeQuery(1, 1, n, l, r) << '\n';
        }
    }
    return 0;
}

代码要点：

• 堆式存储：节点 $k$ 的左孩子是 $2k$，右孩子是 $2k+1$，无需显式存储指针。
• pushdown 必须在 rangeAdd 和 rangeQuery 进入孩子节点之前调用，否则孩子看到的是过时数据。
• pushdown 后孩子的 lazy 是累加而非赋值，因为孩子可能本身已有懒标记。
• build 函数等价于对所有叶子做单点赋值再合并，复杂度 $O(N)$。
• 所有与和相关的变量使用 long long（tree[]、lazy[]、查询返回值）。

---

五、总结

维度	内容
核心思想	基于分治策略，将数组递归对半拆分为二叉树，每个节点存储对应区间的聚合信息。查询和修改都只需访问 $O(\log N)$ 个节点。
构建思路	完全复用归并排序的递归拆分框架，将"合并排序结果"替换为"合并区间信息"。
适用场景	需要同时支持区间修改和区间查询的问题；区间信息需要满足结合律（如求和、最值、GCD、矩阵乘法等）。
优势	单次操作 $O(\log N)$；支持懒标记下的复杂区间操作（加、乘、赋值等，可叠加多个标记）；比树状数组适用范围更广。
局限	实现比树状数组复杂（约 50 行核心代码）；常数比树状数组大；区间信息必须满足结合律；空间占用 $4N$，比树状数组的 $N$ 大。
进阶延伸	主席树（可持久化线段树）、线段树合并、动态开点线段树、线段树优化 DP、扫描线算法
时间复杂度	建树 $O(N)$，单次操作 $O(\log N)$，总计 $O(N + Q \log N)$

一句话：线段树是处理区间问题的核心工具——比树状数组功能更强，是区间数据结构中的必学内容。

---

六、常见 Debug 指南

WA（答案错误）

错误现象	可能原因	排查方法
区间修改后查询结果偏小或偏大	懒标记未下推，孩子的 tree 是过时的	确认 rangeQuery 和 rangeAdd 进入孩子前都调用了 pushdown
区间修改后部分元素值始终为 $0$	pushdown 中传给孩子的标记用了赋值而非累加	确认孩子 lazy 的更新是 lazy[child] += lazy[k] 而非 =
单点修改后区间查询结果不正确	build 遗漏了对某些叶子节点的初始化	确认 build 的递归终止条件（if (l == r)）正确初始化了叶子的值
所有查询结果都为 $0$	查询的单位元返回值不正确	求和返回 $0$，求最大值返回极小值（如 -1e18），确保被剪枝的节点不干扰结果
大样例通过但正式提交 WA	int 溢出	检查 tree[]、lazy[]、查询结果的类型是否为 long long
修改的区间跨过 mid 但只递归了一边	条件写成了 if (ql <= mid) ... else if (qr > mid)	确认两个条件各自独立 if，不要用 else if——区间可能同时跨越左右

TLE（超时）

错误现象	可能原因	排查方法
区间修改极慢（比暴力还慢）	懒标记失效：没有在完全覆盖时 return，继续向下递归	确认 rangeAdd 在 ql <= l && r <= qr 时更新后就 return 了
递归深度极深	mid 计算错误或左右区间范围没缩小（如写成 [l, mid] 和 [mid, r]）	左右区间应为 [l, mid] 和 [mid+1, r]，确保每次递归区间长度严格减小
未关闭同步流	大量 I/O 拖慢	确认 main 开头有 ios::sync_with_stdio(false); cin.tie(nullptr);

RE（运行时错误）

错误现象	可能原因	排查方法
段错误 / 数组越界	MAXN * 4 不够大，或递归时节点编号超出数组范围	确保 tree 和 lazy 大小至少为 MAXN * 4 + 5
递归爆栈	$N$ 接近 $2\times 10^5$ 时树高约 $18$，通常不会爆栈；但若树退化为链会	检查 mid 的计算是否正确，左右区间划分是否保证每次减半
l > r 时仍在递归	查询或修改时 ql 和 qr 的关系出错	确认调用时传入的 ql 和 qr 来自输入，且 $ql \le qr$

通用排查思路

1. 先验证建树：在 build 完成后打印 tree[1]（根节点），确认它等于数组所有元素的总和。
2. 再验证单点操作：先只测试单点修改 + 区间查询（用纯暴力对拍），确认基本结构正确。
3. 然后加入懒标记：在单点操作验证通过后，测试区间修改，观察 pushdown 是否在正确的位置被调用。
4. 对拍验证：写一个 $O(N)$ 的纯暴力，与小数据下的线段树代码跑相同的随机输入，对比输出。这是发现边界错误最有效的方法。