Fenwick Tree or Binary Index Tree

class NumArray:
    global n,A,lsb
    n=None
    A=None

    #following func caluculates LSB left most significant bit
    lsb=lambda y:y&-y
    nums=None
    def __init__(self, x: List[int]):
        global lsb,A,n,nums
        nums=x
        n=len(x)
        A=[0]*(n+1)
    #since fenwick tree starts with index 1  when we refer to corresponding numbs will be i-1(0 base indexed)
        #Add nums[i-1] to  A[i]
        for i in range(1,n+1):
            A[i]=A[i]+x[i-1]

            #find child using parent
            j=i+lsb(i)

        #update child or propagate to child
            if j<n+1:
                A[j]=A[j]+A[i]
    #update index i to val
    def update(self, i: int, val: int) -> None:
        #since we have to update ith element of nums array.
        #It corresponds to branch with i+1 th element of fen tree
        #Before you update nums array,find out delta(change)
        global lsb,A,n,nums

        inc=val-nums[i]
        nums[i]=val

        #j is pointer to corresponding of i in fen tree
        j=i+1

        #while no more child
        while j<n+1:
            #update
            A[j]=A[j]+inc

            #find next child
            j=j+lsb(j)
       # print(nums)
        #print(A)

    #caluculte sum between i and j indexes including i,j
    def sumRange(self, i: int, j: int) -> int:
        global lsb,A,n
        def prefix(i):
            #pointer to fen tree
            j=i+1
            ans=0
            #If no more  parent
            while j>0:
                ans=ans+A[j]
                #find next parent
                j=j-lsb(j)
            return ans
        return prefix(j)-prefix(i-1)


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