线段树python 蓝桥杯

线段树（Segment Tree），也称为区间树，是一种数据结构，用于高效地支持区间查询和修改操作。它通常用来解决一些涉及区间范围的问题，例如求区间内的最大值、最小值、和等。在Python中，线段树通常是通过递归构建和维护的。

蓝桥杯是一系列的全国青少年信息科技竞赛，其中包括算法题目的考察。如果涉及到线段树的题目，可能会让选手实现线段树的数据结构，并用它来解决类似于数组区间查询、更新等问题。例如，给定一个整数数组，你需要能够快速查询任意区间的和，或者在一个范围内添加或删除元素并保持查询结果的正确。

以下是简单的Python线段树构造和操作示例：

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.size = 1 << (len(arr) - 1).bit_length()
        self.tree = [0] * (2 * self.size)

    def build(self, index, start, end):
        if start == end:
            self.tree[index] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(2 * index, start, mid)
            self.build(2 * index + 1, mid + 1, end)
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

# 示例用法
arr = [1, 3, 5, 7, 9]
tree = SegmentTree(arr)
tree.build(1, 0, len(arr) - 1)  # 构建树

# 查询区间和
def query(start, end):
    return self.query(1, start, end, 0, len(arr) - 1)

# 更新区间
def update(start, end, val):
    self.update(1, start, end, val, 0, len(arr) - 1)