线段树（Segment Tree） 描述 线段树是一种二叉树数据结构，用于高效处理数组的区间查询和区间更新操作。它特别适用于需要频繁查询和更新数组某个区间信息（如区间和、区间最大值、区间最小值等）的场景。线段树将整个数组区间递归地划分成若干个子区间，每个树节点存储一个特定区间的聚合信息。通过这种结构，区间查询和区间更新的时间复杂度都能达到O(log n)。 基本概念与结构 问题场景 ：假设有一个数组arr，需要支持两种操作：(1)查询区间[ L, R]的和（或最大值等）；(2)将区间[ L, R ]内的每个元素增加一个值。朴素方法中，查询需要O(n)时间，更新也需要O(n)。线段树旨在将这两种操作优化到O(log n)。 树结构构建 ： 线段树是一棵近似的完全二叉树（通常用数组存储以节省空间）。 根节点表示整个数组区间[ 0, n-1 ]。 每个非叶子节点表示一个区间[ L, R]，将其平分为两半：左子节点区间为[ L, mid]，右子节点区间为[ mid+1, R ]，其中mid = (L + R) // 2。 叶子节点表示长度为1的区间（即单个元素）。 每个节点存储其对应区间的聚合值（例如区间和）。 示例 ：对于数组arr = [ 1, 3, 5, 7, 9, 11 ]，构建求和线段树的过程如下： 根节点表示区间[ 0,5 ]，值为区间和36。 左子节点表示[ 0,2]，值为1+3+5=9；右子节点表示[ 3,5 ]，值为7+9+11=27。 递归划分直到叶子节点（如[ 0,0 ]值为1）。 线段树的构建 递归构建 ：从根节点开始，递归地创建左右子树，直到区间长度为1时设置叶子节点值。 节点值计算 ：非叶子节点的值由其左右子节点的值聚合得到（例如求和时，父节点值=左子节点值+右子节点值）。 时间复杂度 ：构建树需要初始化所有节点，共有约2n个节点（实际为2n-1），因此构建时间为O(n)。 区间查询操作 查询过程 ：查询区间[ L, R ]的和时，从根节点开始递归： 若当前节点区间完全包含在[ L, R ]内，直接返回该节点存储的聚合值。 若当前节点区间与[ L, R ]无重叠，返回0（对求和而言）。 若当前节点区间部分重叠[ L, R ]，则递归查询左右子树，合并结果（如求和时相加）。 示例 ：查询[ 1,4 ]的和（即3+5+7+9=24）： 根节点[ 0,5 ]部分重叠，查询左右子树。 左子树[ 0,2]：区间[ 1,4]与[ 0,2]部分重叠，继续递归。其右子树[ 1,2]完全包含于[ 1,4 ]，返回值3+5=8。 右子树[ 3,5]：区间[ 3,4]完全包含于[ 3,5 ]，返回值7+9=16。 合并结果：8+16=24。 效率 ：每次查询最多遍历树的两条路径，深度为O(log n)，因此时间复杂度为O(log n)。 区间更新操作 懒惰传播（Lazy Propagation） ：直接更新每个叶子节点效率低（O(n)）。引入懒惰标记（Lazy Tag）： 更新区间[ L, R]时，若当前节点区间完全包含在[ L, R ]内，则更新该节点值，并设置懒惰标记（表示子节点待更新）。 查询或更新过程中，若当前节点有懒惰标记，先将标记下推给子节点（更新子节点值和标记），再清除当前标记。 更新步骤 ： 检查当前节点区间与更新区间的重叠情况（类似查询）。 完全包含时，更新节点值并设置懒惰标记。 部分重叠时，先下推懒惰标记（如果需要），再递归更新左右子树，最后更新当前节点值（基于子节点新值）。 示例 ：将区间[ 1,3 ]的每个元素加2： 根节点[ 0,5 ]部分重叠，下推标记（无操作），递归更新左右子树。 左子树[ 0,2]：部分重叠，递归后更新其右子树[ 1,2]（完全包含），节点值增加(2+2)* 2=8（区间长度2，每个元素加2），设置懒惰标记。 右子树[ 3,5]：部分重叠，递归更新其左子树[ 3,3 ]（完全包含），节点值增加2，设置标记。 回溯更新根节点值。 时间复杂度 ：使用懒惰标记后，更新操作也优化为O(log n)。 应用场景与变体 线段树适用于区间求和、区间最值、区间赋值等问题。 变体包括：二维线段树（处理矩阵）、持久化线段树（支持历史版本查询）等。 通过线段树，区间查询和更新操作均被优化到对数时间复杂度，是解决区间类问题的核心数据结构之一。