线段树的区间更新与懒惰传播（Lazy Propagation）优化

线段树是一种用于高效处理区间查询（如区间和、区间最小值等）的数据结构。当涉及区间更新（如将整个区间的每个元素都加上一个值）时，如果逐个更新叶子节点，时间复杂度会退化为O(n)，失去了线段树的优势。懒惰传播（Lazy Propagation）是一种优化技术，它延迟对节点的实际更新，只在必要时才进行，从而将区间更新的时间复杂度保持在O(log n)。

1. 问题描述
假设有一个数组，需要支持两种操作：

• 区间更新：将区间[L, R]内的每个元素增加一个值val。
• 区间查询：查询区间[L, R]的和（或最小值、最大值等）。
  如果每次区间更新都递归到叶子节点逐个修改，效率很低。懒惰传播通过在非叶子节点上记录“待更新的值”，在后续查询或更新真正需要时才传递这些值，避免不必要的操作。

2. 线段树节点设计
每个节点需要存储：

• 区间信息：如区间和sum。
• 懒惰标记：lazy，表示该节点对应区间内每个元素都需要增加的值，但尚未传递给子节点。

struct SegmentTreeNode {
    int sum;  // 区间和
    int lazy; // 懒惰标记
    int left, right; // 节点代表的区间范围[left, right]
};

3. 懒惰传播的核心思想

• 当更新区间[L, R]时，如果当前节点区间完全包含于[L, R]内，则直接更新当前节点的sum，并设置lazy标记，表示其子节点尚未更新。
• 如果当前节点区间与[L, R]部分重叠，则先将lazy标记传递给子节点（递归更新子节点），再更新当前节点的sum。
• 查询时类似：若当前节点有lazy标记，先传递标记再查询。

4. 懒惰传播的步骤
步骤1：初始化线段树

• 构建线段树，初始化每个节点的sum为对应区间的和，lazy为0。

步骤2：区间更新操作

1. 检查懒惰标记传递：若当前节点有lazy标记（lazy != 0），先更新当前节点的sum（sum += lazy * (right - left + 1)），然后将lazy标记传递给左右子节点（子节点的lazy加上该值），最后将当前节点的lazy重置为0。
2. 判断区间包含关系：
   • 若当前节点区间完全包含于更新区间内，则更新当前节点的sum（sum += val * (right - left + 1)），并设置lazy标记（lazy += val），返回。
   • 若当前节点区间与更新区间无重叠，直接返回。
   • 若部分重叠，则递归更新左右子节点，然后根据子节点的新值更新当前节点的sum。

步骤3：区间查询操作

1. 先传递懒惰标记（同更新操作的步骤1）。
2. 判断区间包含关系：
   • 若当前节点区间完全包含于查询区间，直接返回sum。
   • 若无重叠，返回0。
   • 若部分重叠，递归查询左右子节点并返回和。

5. 示例
假设数组为[1, 3, 5, 7, 9, 11]，初始线段树存储区间和。

• 更新区间[0, 2]（前三个元素）各加2：
  • 根节点[0,5]部分重叠，先传递标记（无标记），然后递归左右子节点。
  • 左子节点[0,2]完全包含，更新其sum（原和9 → 9+2*3=15），设置lazy=2。
  • 右子节点[3,5]无重叠，不更新。
  • 根节点sum更新为15+右子节点和27=42。
• 查询区间[0,1]的和：
  • 根节点[0,5]部分重叠，传递标记（无标记），递归左子节点[0,2]。
  • 节点[0,2]有lazy=2，先更新自身sum=15，传递标记给子节点[0,1]和[2,2]（它们的lazy加2），自身lazy重置为0。
  • 节点[0,1]完全包含于查询区间，返回其sum（原和4 → 4+2*2=8）。

6. 时间复杂度分析

• 每次更新或查询最多访问O(log n)个节点，且每个节点的操作是O(1)，因此总时间复杂度为O(log n)。

通过懒惰传播，线段树在保持区间查询高效的同时，大幅提升了区间更新的性能。