class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums=nums
        self.size=size=len(nums)
        h=int(math.ceil(math.log(size,2))) if size else 0
        maxSize=2**(h+1)-1
        self.st=[0]*maxSize
        if size:
            self.initST(0,size-1,0)

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        if i<0 or i>=self.size:
            return
        diff=val-self.nums[i]
        self.nums[i]=val
        self.updateST(0,self.size-1,i,diff,0)

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i<0 or j<0 or i>=self.size or j>=self.size:
            return 0
        return self.sumRangeST(0,self.size-1,i,j,0)
    
    def initST(self,ss,se,si):
        if ss==se:
            self.st[si]=self.nums[ss]
        else:
            mid=(ss+se)/2
            self.st[si]=self.initST(ss,mid,2*si+1)+self.initST(mid+1,se,2*si+2)
        return self.st[si]
    
    def updateST(self,ss,se,i,diff,si):
        if i<ss or i>se:
            return
        self.st[si]+=diff
        if ss!=se:
            mid=(ss+se)/2
            self.updateST(ss,mid,i,diff,2*si+1)
            self.updateST(mid+1,se,i,diff,2*si+2)
    
    def sumRangeST(self,ss,se,qs,qe,si):
        if qs<=ss and qe>=se:
            return self.st[si]
        if se<qs or ss>qe:
            return 0
        mid=(ss+se)/2
        return self.sumRangeST(ss,mid,qs,qe,2*si+1)+self.sumRangeST(mid+1,se,qs,qe,2*si+2)
        


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)