def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: int
        """
        i += self.ls
        self.tree[i] = val
        while i > 0:
            left = right = i
            if i % 2 == 0:
                right = i + 1
            else:
                left = i -1
            self.tree[i / 2] = self.tree[left] + self.tree[right]
            i /= 2

        :type i: int
        :type val: int
        :rtype: int
        
python/307_Range_Sum_Query_Mutable.py