Python中的树形数据结构: 线段树

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

    def build_tree(self, node, start, end):
        if start == end:
            self.tree[node] = self.nums[start]
        else:
            mid = (start + end) // 2
            self.build_tree(2 * node + 1, start, mid)
            self.build_tree(2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def update(self, index, val):
        self.nums[index] = val
        self.update_tree(0, 0, len(self.nums) - 1, index, val)

    def update_tree(self, node, start, end, index, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if index <= mid:
                self.update_tree(2 * node + 1, start, mid, index, val)
            else:
                self.update_tree(2 * node + 2, mid + 1, end, index, val)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, left, right):
        return self.query_tree(0, 0, len(self.nums) - 1, left, right)

    def query_tree(self, node, start, end, left, right):
        if right < start or end < left:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        return self.query_tree(2 * node + 1, start, mid, left, right) + self.query_tree(2 * node + 2, mid + 1, end, left, right)


nums = [ord(c) for c in "pidancode.com"]
tree = SegmentTree(nums)
print(tree.query(0, len(nums) - 1))
tree.update(0, ord('皮'))
print(tree.query(1, 5))

1632
443