线段树核心原理及可视化

labuladong原创约 1363 字

前置知识

阅读本文前，你需要先学习：

一句话总结

线段树是二叉树结构的衍生，用于高效解决区间查询和动态修改问题，其中区间查询的时间复杂度为 $O(\log N)$ ，动态修改单个元素的时间复杂度为 $O(\log N)$ 。

可视化面板支持创建和使用线段树，下面的可视化面板展示了线段树的逻辑结构、底层数组和基本操作 query, update：

考虑到这是第一章，我并不准备深入讲解线段树的实现细节，而是带你了解线段树的基本原理以及应用场景，让你对线段树有一个直观的认识。具体的代码实现安排在二叉树系列习题章节后面的数据结构设计章节，这里没必要深入。

下面让我从选择排序中提到的一种优化思路开始，逐步引出线段树的原理，以及我们为什么需要线段树这种数据结构。

前情回顾

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