LC.307. Range Sum Query - Mutable

class NumArray(object):
	#二叉索引树
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
        self.C = [0] * (len(nums) + 1)
        for i in range(1,len(self.C)):
            for j in range(i - self.lowbit(i)+1, i+1):
                self.C[i] += self.nums[j-1]


    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: None
        """
        old_val = self.nums[i]
        self.nums[i] = val
        i += 1
        while(i < len(self.C)):
            self.C[i] += val - old_val
            i += self.lowbit(i)

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        tmp = self.nums[i]
        i,j =i+1, j+1
        start_sum, end_sum = 0, 0
        while(i > 0):
            start_sum += self.C[i]
            i -= self.lowbit(i)
        while(j > 0):
            end_sum += self.C[j]
            j -= self.lowbit(j)
        return end_sum - start_sum + tmp

    def lowbit(self, x):
        return x & -x