class SegmentTree(object):

    def __init__(self, nums):
        self.l = len(nums)
        self.tree = [0] * self.l + nums
        for i in range(self.l - 1, 0, -1):
            self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

    def setVal(self, i, val):
        n = self.l + i
        self.tree[n] = val
        while n > 1:
            self.tree[n >> 1] = self.tree[n] + self.tree[n ^ 1]
            n >>= 1

    def updata(self, i, val):
        n = self.l + i
        tmp = self.tree[n]
        self.setVal(i, tmp + val)

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


if __name__ == '__main__':
    tree = SegmentTree([1, 2, 2, 3, 4])
    print(tree.sumRange(0, 2))
    tree.update(1, 3)
    print(tree.sumRange(0, 2))
