线段树（Segment Tree）的区间更新操作（加法与乘法复合操作）详解

题目/知识点描述

线段树是一种用于高效处理区间查询和区间更新的数据结构。我们已经掌握了对单一区间（如加法或乘法）的更新操作，但在实际应用中，一个区间可能需要同时进行“加法”和“乘法”两种操作，且操作顺序会影响结果。本专题将深入讲解线段树如何支持**“区间加一个数、区间乘一个数、区间求和”**这三种复合操作，并解决懒标记（Lazy Propagation）在复合操作下的更新与传递问题。

核心难点与解决思路

单一懒标记（如只记录加法增量）易于实现。但加法与乘法结合时，两种操作的顺序会导致结果不同，例如：先加后乘与先乘后加，结果不同。为了正确合并多次更新操作，我们需要设计能记录“乘法和加法复合信息”的懒标记，并在传递时确保操作顺序的一致性和正确性。

解题过程

步骤1：定义数据结构

我们需要在线段树每个节点存储以下信息：

• sum：当前节点对应区间的元素和。
• mul：乘法懒标记，表示该区间内所有元素需要先乘以此值。
• add：加法懒标记，表示乘法操作完成后，再给区间内每个元素加上此值。

class SegTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.sum = 0
        self.mul = 1
        self.add = 0

初始化时，乘法标记mul=1（乘法单位元），加法标记add=0（加法单位元）。

步骤2：操作顺序的约定

为了简化问题，我们规定操作顺序为：先进行乘法，再进行加法。
设对区间每个元素x的操作为：x = x * mul + add。
这个顺序固定后，可以确保多次操作的合并具有一致性。

示例：先执行(mul1, add1)，再执行(mul2, add2)，合并后的操作为：

• 第一步：x = x * mul1 + add1
• 第二步：x = (x * mul1 + add1) * mul2 + add2 = x * (mul1 * mul2) + (add1 * mul2 + add2)
  所以合并后的标记为：
• mul = mul1 * mul2
• add = add1 * mul2 + add2

步骤3：懒标记的下推（pushdown）

当下推懒标记到子节点时，需要更新子节点的sum、mul、add，并遵循“先乘后加”规则。

def pushdown(node):
    left = node.left
    right = node.right
    
    # 更新左子节点
    left.sum = left.sum * node.mul + node.add * (left.r - left.l + 1)
    left.mul *= node.mul
    left.add = left.add * node.mul + node.add
    
    # 更新右子节点
    right.sum = right.sum * node.mul + node.add * (right.r - right.l + 1)
    right.mul *= node.mul
    right.add = right.add * node.mul + node.add
    
    # 重置当前节点懒标记
    node.mul = 1
    node.add = 0

注意：在更新子节点的加法标记时，需先将子节点原有的加法标记乘以父节点的乘法标记，再加上父节点的加法标记，以符合合并公式add_child = add_child * mul_parent + add_parent。

步骤4：区间更新操作（update）

• 如果当前节点区间完全在查询区间内，则直接更新当前节点的sum、mul、add。
• 否则，先执行pushdown确保子节点信息最新，然后递归更新子区间，最后更新当前节点的sum。

def update(node, l, r, mul_val, add_val):
    if l <= node.l and node.r <= r:  # 完全覆盖
        node.sum = node.sum * mul_val + add_val * (node.r - node.l + 1)
        node.mul *= mul_val
        node.add = node.add * mul_val + add_val
        return
    
    pushdown(node)  # 下推懒标记
    
    mid = (node.l + node.r) // 2
    if l <= mid:
        update(node.left, l, r, mul_val, add_val)
    if r > mid:
        update(node.right, l, r, mul_val, add_val)
        
    node.sum = node.left.sum + node.right.sum

步骤5：区间查询操作（query）

查询时需要下推懒标记，确保子区间信息正确。

def query(node, l, r):
    if l <= node.l and node.r <= r:
        return node.sum
        
    pushdown(node)
    
    res = 0
    mid = (node.l + node.r) // 2
    if l <= mid:
        res += query(node.left, l, r)
    if r > mid:
        res += query(node.right, l, r)
    return res

步骤6：特殊情况的处理

• 纯加法操作：可视为(mul=1, add=c)。
• 纯乘法操作：可视为(mul=c, add=0)。
• 操作取模：在实际问题中，sum、mul、add可能需要对某个大数取模，每一步计算都需要及时取模，防止溢出。

总结与应用场景

通过设计支持乘法和加法复合操作的懒标记，线段树可以高效处理更复杂的区间更新问题，例如：

• 动态维护区间线性变换（ax+b）后的和。
• 解决序列的区间批量修改与区间求和问题，常见于竞赛题目（如“线段树模板题”）。

核心要点：

1. 固定操作顺序（先乘后加）。
2. 推导出复合操作的合并公式。
3. 在下推标记时，需同时更新子节点的懒标记，并遵循合并公式。

通过本专题，你不仅掌握了线段树复合更新的实现细节，也理解了懒标记设计的普适思想，可推广到其他复合操作（如先加后乘、区间赋值与加法结合等）。