zkw线段树 python

下面是一个基于线段树实现区间修改和区间查询的Python代码:

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.tree = [0] * (4 * len(arr))
        self.lazy = [0] * (4 * len(arr))
        self.build(0, len(arr)-1, 0)
    
    def build(self, start, end, node):
        if start == end:
            self.tree[node] = self.arr[start]
        else:
            mid = (start + end) // 2
            self.build(start, mid, 2*node + 1)
            self.build(mid+1, end, 2*node + 2)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]
    
    def update(self, start, end, node, l, r, val):
        if self.lazy[node] != 0:
            self.tree[node] += ((end - start + 1) * self.lazy[node])
            if start != end:
                self.lazy[2 * node + 1] += self.lazy[node]
                self.lazy[2 * node + 2] += self.lazy[node]
            self.lazy[node] = 0
        
        if start > r or end < l:
            return
        
        if start >= l and end <= r:
            self.tree[node] += ((end - start + 1) * val)
            if start != end:
                self.lazy[2 * node + 1] += val
                self.lazy[2 * node + 2] += val
            return
        
        mid = (start + end) // 2
        self.update(start, mid, 2 * node + 1, l, r, val)
        self.update(mid + 1, end, 2 * node + 2, l, r, val)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def query(self, start, end, node, l, r):
        if self.lazy[node] != 0:
            self.tree[node] += ((end - start + 1) * self.lazy[node])
            if start != end:
                self.lazy[2 * node + 1] += self.lazy[node]
                self.lazy[2 * node + 2] += self.lazy[node]
            self.lazy[node] = 0
        
        if start > r or end < l:
            return 0
        
        if start >= l and end <= r:
            return self.tree[node]
        
        mid = (start + end) // 2
        left = self.query(start, mid, 2 * node + 1, l, r)
        right = self.query(mid + 1, end, 2 * node + 2, l, r)
        return left + right

这个代码实现了一个SegmentTree类，通过build方法建立线段树，通过update方法对区间进行修改，通过query方法对区间进行查询。其中，lazy数组记录了对区间的延迟修改。具体的使用方法可以参考下面的例子：

arr = [1, 3, 5, 7, 9, 11]
tree = SegmentTree(arr)

print(tree.query(0, len(arr)-1, 0, 1, 4)) # 25
tree.update(0, len(arr)-1, 0, 2, 4, 2)
print(tree.query(0, len(arr)-1, 0, 1, 4)) # 31