148ms Fast python solution using BIT


  • -1
    V
    class NumArray(object):
        def __init__(self, nums):
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            self.numArray=[0]
            for self.length, n in enumerate(nums, start=1):
                if self.length&1:
                    self.numArray.append(n)
                else:
                    self.numArray.append(self.sumRange(self.length-(-self.length&self.length), self.length-2)+n)
    
        def update(self, i, val):
            """
            :type i: int
            :type val: int
            :rtype: int
            """
            val-=self.sumRange(i, i)
            i+=1
            
            while i<=self.length:
                self.numArray[i]+=val
                i+=-i&i
            
        def sumRange(self, i, j):
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            j+=1
            sum=0
            while j!=i:
                if j>i:
                    sum+=self.numArray[j]
                    j-=-j&j
                else:
                    sum-=self.numArray[i]
                    i-=-i&i
            return sum

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.