编辑“︁线段树”︁（章节）

== 应用场景 ==
线段树适用于以下问题：
1. '''区间求和/最值查询'''：如统计数组子数组的和或最大值。
2. '''区间更新'''：如将区间内的所有元素增加一个固定值（需结合'''懒惰传播'''技术）。
3. '''动态数据维护'''：当数据频繁更新时，线段树比前缀数组更高效。

=== 实际案例 ===
'''问题'''：给定一个数组，支持以下操作：
1. 查询区间<math>[l, r]</math>的和。
2. 将区间<math>[l, r]</math>的所有元素增加<math>\Delta</math>。

'''解决方案'''：使用带懒惰传播的线段树。

<syntaxhighlight lang="python">
class LazySegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        # 填充叶子节点
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        # 构建非叶子节点
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def push(self, node, node_l, node_r):
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node] * (node_r - node_l + 1)
            if node < self.size:  # 非叶子节点
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0

    def range_update(self, l, r, delta, node=1, node_l=0, node_r=None):
        if node_r is None:
            node_r = self.size - 1
        self.push(node, node_l, node_r)
        if r < node_l or l > node_r:
            return
        if l <= node_l and node_r <= r:
            self.lazy[node] += delta
            self.push(node, node_l, node_r)
            return
        mid = (node_l + node_r) // 2
        self.range_update(l, r, delta, 2 * node, node_l, mid)
        self.range_update(l, r, delta, 2 * node + 1, mid + 1, node_r)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def range_query(self, l, r, node=1, node_l=0, node_r=None):
        if node_r is None:
            node_r = self.size - 1
        self.push(node, node_l, node_r)
        if r < node_l or l > node_r:
            return 0
        if l <= node_l and node_r <= r:
            return self.tree[node]
        mid = (node_l + node_r) // 2
        return self.range_query(l, r, 2 * node, node_l, mid) + \
               self.range_query(l, r, 2 * node + 1, mid + 1, node_r)

# 示例使用
arr = [1, 2, 3, 4]
lst = LazySegmentTree(arr)
print(lst.range_query(1, 3))  # 输出: 9
lst.range_update(1, 3, 2)     # 区间[1,3]每个元素加2
print(lst.range_query(1, 3))  # 输出: 15 (4 + 5 + 6)
</syntaxhighlight>