python 线段树模板

class NumArray:

    def __init__(self, nums: List[int]):
        n = 1
        while n<len(nums):
            n<<=1
        self.n = n
        self.tree = [0]*self.n + nums + [0]*(self.n-len(nums))
        for i in range(self.n-1,0,-1):
            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]

    def update(self, i: int, val: int) -> None:
        i = self.n + i
        diff = val - self.tree[i]
        while i>0:
            self.tree[i] += diff
            i//=2


    def sumRange(self, i: int, j: int) -> int:
        i = i+self.n 
        j = j+self.n
        res = 0
        while i<=j:
            if i%2 == 1:
                res += self.tree[i]
                i+=1
            if j%2 == 0:
                res += self.tree[j]
                j-=1
            i,j = i//2,j//2
        return res