线段树（Segment Tree）的区间查询与更新操作详解 线段树是一种用于处理区间查询和区间更新问题的高效数据结构。它将一个区间划分成多个小区间，每个树节点存储对应区间的聚合信息（如求和、最大值、最小值等），使得区间操作的时间复杂度为O(log n)。 一、线段树的基本结构 线段树是一棵平衡二叉树，每个叶子节点对应原始数组的一个元素，每个非叶子节点代表其左右子节点区间的合并。例如对于长度为8的数组[ 1,3,5,7,9,11,13,15 ]： 根节点存储区间[ 0,7 ]的和（1+3+...+15=64） 左子节点存储区间[ 0,3 ]的和（1+3+5+7=16） 右子节点存储区间[ 4,7 ]的和（9+11+13+15=48） 二、线段树的构建过程 递归划分区间 ： 从根节点开始（对应整个区间） 将当前区间[ l, r ]平分为两半：mid = (l + r) // 2 左子树对应区间[ l, mid]，右子树对应区间[ mid+1, r ] 递归构建直到区间长度为1（叶子节点） 合并子节点信息 ： 非叶子节点的值 = 左子节点值 + 右子节点值（求和场景） 对于最大值查询：节点值 = max(左子节点值, 右子节点值) 三、区间查询操作（以求和为例） 查询区间[ q_ l, q_ r ]的求和值： 从根节点开始递归查询 如果当前节点区间[ l, r]完全包含在查询区间内（q_ l ≤ l 且 r ≤ q_ r），直接返回节点值 如果当前节点区间与查询区间部分重叠： 计算中点mid = (l + r) // 2 初始化结果res = 0 如果查询区间与左子树有重叠（q_ l ≤ mid），递归查询左子树 如果查询区间与右子树有重叠（q_ r > mid），递归查询右子树 返回左右子树查询结果之和 四、点更新操作 更新位置index的值： 从根节点开始递归查找 如果到达叶子节点（l == r），更新节点值 否则根据index与中点mid的关系选择左子树或右子树 递归返回时更新父节点值（父节点值 = 左子节点值 + 右子节点值） 五、区间更新与懒惰传播 当需要更新整个区间时，使用懒惰传播优化： 懒惰标记 ：每个节点维护一个标记，表示"该区间所有元素需要增加的值" 更新过程 ： 如果当前区间完全包含在更新区间内，更新当前节点值并设置懒惰标记 否则先下推标记到子节点，再递归更新左右子树 标记下推 ： 将当前节点的懒惰标记值加到子节点标记上 更新子节点值：子节点值 += 标记值 × 子区间长度 清除当前节点的标记 六、时间复杂度分析 构建：O(n) - 每个节点处理一次 区间查询：O(log n) - 树的高度 点更新：O(log n) - 单路径更新 区间更新（带懒惰传播）：O(log n) - 避免遍历所有叶子 线段树通过将区间操作转化为对数级别的节点访问，为各种区间问题提供了高效的解决方案，是算法竞赛和工程实践中重要的数据结构。