线段树核心原理及可视化

考虑到这是第一章，我并不准备深入讲解线段树的实现细节，具体代码会在后面的数据结构设计章节介绍。不过这里可以借助可视化面板帮你直观感受一下线段树的几种变化。

首先，基本的线段树 包含区间查询 query 和单点修改 update 方法，你可以打开这个可视化面板，逐行点击代码，观察 query 和 update 方法的执行过程：

可以看到这棵二叉树的叶子节点是数组中的元素，非叶子节点就是索引区间（线段）的汇总信息，也就是「线段树」这个名字的由来。

但上面这个线段树有个问题，就是必须输入 nums 数组进行构建，如果我们想在一个非常长的区间上进行区间操作，比如 [0, 10^9]，那么上来就需要 $10^9$ 的空间复杂度构建线段树，这是非常浪费的。

动态线段树的实现 运用「动态开点」技巧优化线段树处理稀疏数据的内存开销。你可以打开这个可视化面板，逐行点击代码，观察线段树的动态构建过程：

上面的实现都只支持「单点更新」，但更通用的需求是区间更新，比如把索引区间 [i, j] 的元素都更新为 val。懒更新线段树的实现 运用「懒更新」技巧，给线段树新增 rangeAdd/rangeUpdate 方法，可以在 $O(\log N)$ 时间复杂度内完成任意长度的区间更新。

你可以打开这个可视化面板，逐行点击代码，观察懒更新线段树的运行过程，区间更新仅需修改少数几个节点即可完成：

下面我们来介绍线段树的使用场景和核心原理。

使用场景

在 选择排序 中，我们会尝试解决一个需求，就是计算 nums 数组中从索引 i 开始到末尾的最小值。

我们将提出一种使用 suffixMin 数组的优化尝试，即提前预计算一个 suffixMin 数组，使得 suffixMin[i] = min(nums[i..])，这样就可以在 $O(1)$ 时间内查询 nums[i..] 的最小值：