线段树核心原理及可视化
原创约 1756 字
一句话总结
线段树是 二叉树结构 的衍生，用于高效解决区间查询和动态修改的问题，其中区间查询的时间复杂度为 ，动态修改单个元素的时间复杂度为 。
可视化面板支持创建和使用线段树，下面的可视化面板展示了线段树的逻辑结构、底层数组和基本操作 query, update，你可以逐行点击代码，观察树结构的变化：
结合可视化面板应该能够比较直观地理解「线段树」这个名字的由来：这棵二叉树的叶子节点是数组中的元素，非叶子节点就是索引区间（线段）的汇总信息。
考虑到这是第一章，我并不准备深入讲解线段树的实现细节，而是带你了解线段树的基本原理以及应用场景，让你对线段树有一个直观的认识。线段树的代码实现及应用 实现安排在后面的数据结构设计章节，这里没必要深入。
下面让我从 选择排序 中提到的一种优化思路开始，逐步引出线段树的原理，以及我们为什么需要线段树这种数据结构。
前情回顾
在后文 选择排序 中，我们有一个需求，就是计算 nums 数组中从索引 i 开始到末尾的最小值。
当时我们提出过一种使用 suffixMin 数组的优化尝试，即提前预计算一个 suffixMin 数组，使得 suffixMin[i] = min(nums[i..])，这样就可以在 时间内查询 nums[i..] 的最小值：