视频字幕
线段树是一种重要的数据结构，用于解决区间查询问题。当我们需要频繁查询数组中某个区间的信息时，暴力解法每次都要遍历整个区间，时间复杂度为O(n)。线段树通过预处理构建一个完全二叉树结构，将区间分解为更小的子区间，使得查询时间复杂度降低到O(log n)。在线段树中，每个节点存储对应区间的信息，叶子节点存储单个元素，内部节点存储子区间的合并结果。
现在我们来详细演示线段树的构建过程。以数组[1,3,5,7,9,11]为例，首先创建根节点，表示整个区间[0,5]，存储所有元素的和36。然后递归地将区间二分：左子树表示区间[0,2]，和为9；右子树表示区间[3,5]，和为27。继续分解，直到每个叶子节点只包含一个元素。每个内部节点的值都是其子节点值的和，这样就构建出了完整的线段树结构。
现在演示如何在线段树中进行区间查询。以查询区间[2,5]的和为例。从根节点开始，判断当前节点区间与查询区间的关系。根节点[0,5]与查询区间[2,5]部分重叠，需要递归查询子树。左子树[0,2]与查询区间[2,5]有交集，继续递归。右子树[3,5]完全包含在查询区间内，直接返回27。最终找到区间[2,2]的值5，加上区间[3,5]的值27，得到查询结果32。这样，线段树将O(n)的暴力查询优化为O(log n)的高效查询。
现在演示线段树的单点更新操作。假设要将索引2的值从5更新为8。更新算法从根节点开始，沿着路径向下查找到目标叶子节点。找到索引2对应的叶子节点后，将其值从5更新为8。然后向上回溯，重新计算所有祖先节点的值：区间[0,2]的和从9变为12，根节点[0,5]的和从36变为39。这样就完成了单点更新，时间复杂度为O(log n)，保持了线段树数据的一致性。
总结线段树的核心优势和应用场景。线段树具有优秀的时间复杂度：构建O(n)，查询和更新都是O(log n)。相比暴力查询的O(n)时间复杂度，线段树大大提高了效率。相比前缀和数组，线段树支持高效的动态更新。线段树的典型应用包括区间求和、区间最值查询、区间更新等。在股票价格分析、数组统计、游戏排行榜维护等实际场景中都有广泛应用。线段树是解决动态区间查询问题的重要工具，值得深入学习和掌握。