在第11讲中，我们将深入探讨一种非常实用且高效的数据结构——线段树（Segment Tree）。线段树是一种平衡的二叉树数据结构，适合用于处理数组元素的动态和静态区间查询问题，如区间求和、区间最小值等。线段树最常见的应用场景是在频繁请求区间查询和更新的情况下，由于其结构的特殊性，线段树可以在 O(log n) 的时间复杂度内完成查询和更新操作。

线段树的基本概念

线段树是通过将数组二分递归构建而成的，每一个节点代表一个区间的信息，比如区间和、区间最大值等。叶子节点通常表示数组中的一个元素，而内部节点表示其子节点所组成区间的汇总。

线段树的构建

假设我们有一个数组 arr ：

arr = [1, 3, 5, 7, 9, 11]  

我们想要构建一个线段树，使得我们能快速地查询区间和。

class SegmentTree:  
    def __init__(self, data):  
        self.n = len(data)  
        self.tree = [0] * (2 * self.n)  
        # 在叶子节点存储原数组的值  
        for i in range(self.n):  
            self.tree[self.n + i] = data[i]  
        # 构建内部节点  
        for i in range(self.n - 1, 0, -1):  
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]  
    def update(self, index, value):  
        # 先更新叶子节点  
        pos = index + self.n  
        self.tree[pos] = value  
        # 更新父节点  
        while pos > 1:  
            pos //= 2  
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]  
    def query(self, left, right):  
        # 查询区间 [left, right)  
        result = 0  
        left += self.n  
        right += self.n  
        while left < right:  
            if left & 1:  
                result += self.tree[left]  
                left += 1  
            if right & 1:  
                right -= 1  
                result += self.tree[right]  
            left //= 2  
            right //= 2  
        return result  
# 使用示例  
segment_tree = SegmentTree(arr)  
print("Initial sum of [1, 3):", segment_tree.query(1, 3))  # 返回 3 + 5 = 8  
segment_tree.update(1, 10)  
print("After update, sum of [1, 3):", segment_tree.query(1, 3))  # 返回 10 + 5 = 15  

线段树的应用

1. 区间查询：线段树最基本的功能就是快速的区间查询，可以在 O(log n) 时间内完成，而相对于遍历数组的 O(n)，效率极大提升。

2. 动态更新：在线段树上进行单点更新后，可以在同样 O(log n) 的时间内更新整个树，有助于动态调整和维护数据。

3. 空间效率：虽然开销较数组稍大，但线段树使用一个大小为近似 2n 的存储空间，非常适合在需要快速动态查询和更新的场景下。

小结

线段树是一种优化查询与更新操作的优秀数据结构，它在许多竞赛和工程场景中都有广泛的应用。通过对线段树的深入理解与实践，相信大家能在复杂问题的解决上得到帮助。在明白如何构建、更新和查询线段树后，可以尝试在不同的查询场景中使用，如最小值查询、最大值查询等，从而掌握线段树的更多应用。