【数据结构2-2】线段树

如何快速求出一个序列的区间和呢？可以使用前缀和。如何快速求出一个序列的最值呢？可 以使用 ST 表。这两种数据结构在建立的时候颇费功夫，但使用的时候效率很高。如果再增加一 个需求：时不时的修改序列的值，那么这两种数据结构就无法高效完成了。不过可以使用线段树 来解决这类问题。 在基础篇中，我们已经学习了二叉树的有关概念。而线段树是一种特殊的二叉树，它可以将 一个线性的序列组织成一个树状的结构，从而可以在对数的时间复杂度下访问序列上的任意一个 区间并进行维护。在本章中，将学习线段树的构建方法和一些简单的应用。 该题单内容将继续改进。 对应进阶篇第 6 章。