小木的算法日记-线段树

🌳 线段树（Segment Tree）：玩转区间作的终极利器

你好，未来的算法大师！

想象一下，你正在处理一个巨大的数据集，比如某个电商网站一整天的用户点击流。老板突然问你：“下午2点到3点之间，我们的总点击量是多少？” 几分钟后，他又问：“把10点到11点之间的数据，因为系统故障，全部乘以0.5，然后再告诉我下午的总点击量。”

如果用普通的数组，每次查询都需要遍历，每次修改更是灾难。面对这种需求，我们该怎么办？频繁的区间查询和区间修改

答案，就是我们今天的主角——。线段树（Segment Tree）

这篇文章将带你：

直击痛点：理解普通数组在区间问题上的局限性。
掌握神器：了解线段树如何用的时间复杂度解决这些问题。O（对数 N）
展望进阶：一窥线段树的“动态开点”和“懒更新”等高级玩法。

准备好了吗？让我们开始构建这棵神奇的“信息之树”。

😫 The Pain：区间问题的困境

在深入线段树之前，我们先感受一下“没有线段树”时的痛苦。

假设我们有一个数组，需要频繁查询任意区间的最小值。一个常见的优化思路是。比如，我们可以创建一个数组，其中存储这个后缀区间的最小值。数字预计算后缀最小后缀Min[i]nums[i：]

      # 预计算后缀最小值的示例
nums = [3, 1, 4, 2]
# suffixMin[i] 表示 nums[i..] 中的最小值
suffixMin = [0] * len(nums)  ：创建一个和 nums 长度相同的数组，用来存每个位置的「后缀最小值」# 从后往前计算
suffixMin[len(nums) - 1] = nums[len(nums) - 1]  作用：最后一个人的后缀只有自己，所以他的「后缀最小值」就是自己的身高。
for i in range(len(nums) - 2, -1, -1):suffixMin[i] = min(nums[i], suffixMin[i + 1])# suffixMin 会是 [1, 1, 2, 2]
print(suffixMin)# 查询 nums[1..] 的最小值
# O(1) 时间查询，非常快！
print(suffixMin[1]) # 输出 1

这种“前缀和/后缀和”思想很棒，查询效率是，但它有一个：O（1）致命弱点

无法应对动态修改！

一旦中的某个元素改变，比如变了，那么和都需要重新计算。如果数组很大，一次修改可能导致的更新成本，这在高性能场景下是不可接受的。数字数字[1]后缀Min[0]后缀Min[1]O（N）

痛点总结：

静态数组：区间查询慢（），单点更新快（）。O（N）O（1）
预计算数组：特定区间查询快（），但更新慢（）。O（1）O（N）

我们需要一个既能快速查询，又能快速更新的数据结构。于是，线段树应运而生。

✨ The Magic：线段树的核心能力

一句话定义：线段树是一种，它将一个区间分解成若干个子区间，每个节点代表一个区间的“聚合信息”（如和、最值等），从而实现快速的区间操作。平衡二叉树

核心 API 概览（⭐）

一个基础的线段树通常提供以下接口：

      from typing import Callableclass SegmentTree:def __init__(self, nums: list[int], merge: Callable[[int, int], int]):"""构造函数，基于一个数组初始化线段树。时间复杂度: O(N)Args:nums (list[int]): 原始数组。merge (Callable): 一个函数，定义了如何合并两个子区间的信息。例如，求和是 lambda a, b: a + b，求最小值是 lambda a, b: min(a, b)。"""passdef query(self, i: int, j: int) -> int:"""查询闭区间 [i, j] 的聚合值。时间复杂度: O(log N)"""passdef update(self, i: int, val: int):"""将数组中索引 i 的值更新为 val。时间复杂度: O(log N)"""pass

为什么是？O(log N)

树高是 O(log N)：线段树在构建时，总是从中间分割区间，这保证了它是一棵的二叉树。树的高度决定了操作的上限。高度平衡
query 的路径：查询一个区间时，这个大区间可以被巧妙地拆分成树上个节点所代表的小区间。我们只需将这些节点的信息合并即可。[i, j]O(log N)
update 的路径：更新一个叶子节点时，我们只需要沿着从该叶子到根节点的唯一路径，更新路径上的所有父节点。这条路径的长度就是树的高度，即。O(log N)

🚀 The Evolution: 线段树的进阶形态

基础线段树已经很强大了，但在更复杂的场景下，它还有一些更酷的变体。

变体名称	重要性	解决的问题	核心技巧
基础线段树	⭐⭐⭐⭐⭐	区间查询 & 单点更新。面试和竞赛的基础。	分治思想
动态开点线段树	⭐⭐⭐⭐	处理，如，节省内存。超大稀疏区间[0, 10^9]	不预先建树，访问到节点时才创建。
懒更新线段树	⭐⭐⭐⭐⭐	区间更新。例如，将内所有数加。[i, j]val	将更新任务“缓存”在父节点上，需要时再下推。

懒更新 (Lazy Propagation) 举例:
想象一下，要把 [0, 100] 这个区间的所有数都加上 5。我们不必真的去更新 101 个叶子节点。我们只需在代表的那个根节点上贴一个标签：“嘿，我这里的所有子孙后代都要加 5”。[0, 100]

只有当查询操作需要深入到这个节点的子区间时，我们才把这个“懒任务”向下传递一层。这个技巧极大地提升了区间更新的效率，使其也能达到。O(log N)

🧠 学习成果检验 (必会)

现在，检验一下你是否掌握了线段树的核心思想。请尝试回答以下问题：

问题 1：
为什么说线段树是一种“空间换时间”的数据结构？它比原始数组多占用了多少空间？

一句话总结：
线段树就像为数组建了一个 “多层抽屉柜”，用更多抽屉（空间）换更快的查找速度（时间）。

详细解释：

原始数组：比如有 4 个苹果（N=4），放在一排抽屉里，想找区间最小值时，得逐个翻找（O (N) 时间）。
线段树：把 4 个苹果放进一个 3 层的抽屉柜：
- 第 1 层：1 个抽屉（根节点），存 “所有苹果的最小值”。
- 第 2 层：2 个抽屉，分别存 “前 2 个苹果” 和 “后 2 个苹果” 的最小值。
- 第 3 层：4 个抽屉，每个抽屉存 1 个苹果（叶子节点）。
- 总抽屉数：1+2+4=7 个，约是原始数组的 2 倍（实际线段树通常开 4 倍空间，避免越界）。

空间占用结论：

线段树需要 4 倍原始数组大小 的空间（比如 N=100，线段树用 400 个位置），但换来每次查询 / 更新只需 “爬 3 层楼”（O (logN) 时间），比原始数组的 “翻 100 次抽屉”（O (N)）快很多！

问题 2：
如果我想用线段树来解决“查询区间内有多少个偶数”的问题，我应该如何定义中的函数和叶子节点的值？

比喻：分糖果统计
假设每个数字是一颗糖，偶数糖是粉色（值为 1），奇数糖是蓝色（值为 0）。线段树的任务是统计任意区间内的粉色糖数量。

具体做法：

叶子节点：每个叶子对应一个数字，存 “1”（粉色）或 “0”（蓝色）。
- 比如数字4（偶数）→ 叶子存1；数字3（奇数）→ 叶子存0。
merge 函数：父节点把左右子节点的数加起来，就像把两堆糖合起来数总数。
- 左子树有 2 颗粉色糖，右子树有 1 颗→ 父节点存 3 颗。

举个例子：
数组[2, 3, 4, 5] → 叶子节点是[1, 0, 1, 0]。

左子树（前两个数）的和是1+0=1（表示有 1 个偶数）。
右子树（后两个数）的和是1+0=1。
根节点的和是1+1=2，即整个数组有 2 个偶数。

问题 3：
一个朋友告诉你：“我可以用个预计算的前缀和数组，在时间内查询任意区间的和，并且支持的单点更新，这比线段树的查询要快！” 他的说法在什么情况下可能是合理的，又在什么情况下线段树是更优的选择？NO(1)O(N)O(log N)

比喻：图书馆查书 vs 改书

朋友的方法（前缀和）：
- 提前写好一本 “查书手册”，记录从第 1 页到第 i 页的总字数（前缀和）。
- 查书快：想知道第 3 页到第 5 页的总字数，直接用手册计算（O (1) 时间）。
- 改书慢：如果修改第 4 页的字数，需要重写第 4 页之后的所有手册内容（O (N) 时间）。
- 适用场景：图书馆的书很少修改（更新少），但每天有很多人查询（查询多）。
线段树的方法：
- 把书分成章节存进 “多层书架”，每层记录对应章节的总字数。
- 查书和改书都快：修改第 4 页只需更新对应章节的书架（O (logN) 时间），查询时逐层合并结果（O (logN) 时间）。
- 适用场景：如果书经常被修改（比如作业答案频繁更新），线段树更省力。