用python写一个线段树

下面是一个简单的 Python 代码实现，用于构建线段树和查询区间和：

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

    def build(self, index, left, right):
        if left == right:
            self.tree[index] = self.nums[left]
            return
        mid = (left + right) // 2
        self.build(index * 2 + 1, left, mid)
        self.build(index * 2 + 2, mid + 1, right)
        self.tree[index] = self.tree[index * 2 + 1] + self.tree[index * 2 + 2]

    def query(self, index, left, right, query_left, query_right):
        if query_left > right or query_right < left:
            return 0
        if query_left <= left and query_right >= right:
            return self.tree[index]
        mid = (left + right) // 2
        return self.query(index * 2 + 1, left, mid, query_left, query_right) + \
               self.query(index * 2 + 2, mid + 1, right, query_left, query_right)

    def update(self, index, left, right, update_index, update_val):
        if left == right:
            self.tree[index] = update_val
            return
        mid = (left + right) // 2
        if update_index <= mid:
            self.update(index * 2 + 1, left, mid, update_index, update_val)
        else:
            self.update(index * 2 + 2, mid + 1, right, update_index, update_val)
        self.tree[index] = self.tree[index * 2 + 1] + self.tree[index * 2 + 2]

这个代码实现了以下功能：

- 创建一个线段树
- 查询线段树中区间的和
- 更新线段树中一个指定位置的值

这个代码的时间复杂度为 O(log n)，其中 n 是数组的长度。