zkw线段树的python实现

以下是 zkw 线段树的 Python 实现：

class ZkwSegmentTree:
    def __init__(self, n):
        self.sz = 1
        while self.sz < n:
            self.sz <<= 1
        self.tree = [0] * (2 * self.sz)

    def update(self, i, val):
        i += self.sz
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, l, r):
        l += self.sz
        r += self.sz
        ans = 0
        while l <= r:
            if l % 2 == 1:
                ans += self.tree[l]
                l += 1
            if r % 2 == 0:
                ans += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return ans

这里实现了 zkw 线段树的基本操作，包括 `update` 和 `query`。其中 `update(i, val)` 更新位置 `i` 的值为 `val`，`query(l, r)` 查询区间 `[l, r]` 的和。这里的实现采用了数组存储线段树，而非树形结构，使得 zkw 线段树的空间复杂度为 $O(n)$。