线段树python模板

下面是一个简单的线段树的 Python 实现模板：

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.tree = [0] * (4 * len(arr))
        self.build(0, 0, len(arr) - 1)

    def build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            self.build(left_child, start, mid)
            self.build(right_child, mid + 1, end)
            self.tree[node] = self.tree[left_child] + self.tree[right_child]
    
    def query(self, node, start, end, left, right):
        # 区间完全包含在查询区间内
        if left <= start and right >= end:
            return self.tree[node]
        
        # 区间完全不在查询区间内
        if end < left or start > right:
            return 0
        
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        return self.query(left_child, start, mid, left, right) + self.query(right_child, mid + 1, end, left, right)
    
    def update(self, node, start, end, index, value):
        if start == end:
            self.arr[index] = value
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            if start <= index and index <= mid:
                self.update(left_child, start, mid, index, value)
            else:
                self.update(right_child, mid + 1, end, index, value)
            
            self.tree[node] = self.tree[left_child] + self.tree[right_child]

使用这个模板，可以通过以下步骤来构建和使用线段树：

1. 创建一个 SegmentTree 对象，并传入原始数组作为参数。
2. 可以使用 `query` 方法来查询某个区间的和，传入查询区间的左右边界。
3. 可以使用 `update` 方法来更新原始数组中的某个元素，传入元素的索引和新的值。

注意，这只是一个简单的线段树模板，可以根据具体问题的需求进行适当修改和扩展。