Binary Indexed Tree
class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        if not nums:
            return
        self.__nums = nums
        self.__bit = [0] * (len(self.__nums) + 1)
        #calculate prefix sum array
        for i in xrange(1, len(self.__bit)):
            self.__bit[i] = nums[i-1] + self.__bit[i-1]
 #every bit array element store the sum of n number of elements, where n=low bit value 
        #for example bit[7]=bit[111],low bit of 111= 1, bit[7] store the sum of one element counting back from 7 which is nums[6]
        #for example bit[12]=bit[1100],low bit of 1100=4, bit[12] store the sum of four elements counting back from 12 whic is nums[8~11]
        #bit[i] stores low_bit_of_i elements= nums[i-low_bit_of_i]+..+nums[i-1]=prefixsum[i]-prefixsum[i-low_bit_of_i]
        for i in reversed(xrange(1, len(self.__bit))):
            last_i = i - (i & -i)
            self.__bit[i] -= self.__bit[last_i]

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: int
        """
        if val - self.__nums[i]:
            self.__add(i, val - self.__nums[i])
            self.__nums[i] = val
        
    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.__sum(j) - self.__sum(i-1)

    def __sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self.__bit[i]
            i -= (i & -i)
        return ret

    def __add(self, i, val):
        i += 1
        while i <= len(self.__nums):
            self.__bit[i] += val
            i += (i & -i)