Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:


Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8


Note:


       The array is only modifiable by the update function.
       You may assume the number of calls to update and sumRange function is distributed evenly.

Difficulty: interview

Starter code:

class NumArray:
    def __init__(self, nums: List[int]):
    def update(self, i: int, val: int) -> None:
    def sumRange(self, i: int, j: int) -> int:
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

Solutions:
from math import sqrt
 class NumArray(object):
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         if nums:
             k=int(sqrt(len(nums)))
             add,i=[],0
             while i<=len(nums)-k:
                 add.append(sum(nums[i:i+k]))
                 i+=k
             if i!=len(nums):
                 add.append(sum(nums[i:]))
             self.nums,self.add,self.k=nums,add,k
         
 
     def update(self, i, val):
         """
         :type i: int
         :type val: int
         :rtype: void
         """
         self.add[i//self.k]+=val-self.nums[i]
         self.nums[i]=val
         
         
 
     def sumRange(self, i, j):
         """
         :type i: int
         :type j: int
         :rtype: int
         """
         def func(i):
             return sum(self.add[:i//self.k])+sum(self.nums[(i//self.k)*self.k:i+1]) if i>=0 else 0
         return func(j)-func(i-1)
         
 
 
 # Your NumArray object will be instantiated and called as such:
 # obj = NumArray(nums)
 # obj.update(i,val)
 # param_2 = obj.sumRange(i,j)

from math import sqrt
 class NumArray(object):
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         if nums:
             k=int(sqrt(len(nums)))
             add,i=[],0
             while i<=len(nums)-k:
                 add.append(sum(nums[i:i+k]))
                 i+=k
             if i!=len(nums):
                 add.append(sum(nums[i:]))
             self.nums,self.add,self.k=nums,add,k
         
 
     def update(self, i, val):
         """
         :type i: int
         :type val: int
         :rtype: void
         """
         self.add[i//self.k]+=val-self.nums[i]
         self.nums[i]=val
         
         
 
     def sumRange(self, i, j):
         """
         :type i: int
         :type j: int
         :rtype: int
         """
         def func(i):
             return sum(self.add[:i//self.k])+sum(self.nums[(i//self.k)*self.k:i+1]) if i>=0 else 0
         return func(j)-func(i-1)
         
 
 
 # Your NumArray object will be instantiated and called as such:
 # obj = NumArray(nums)
 # obj.update(i,val)
 # param_2 = obj.sumRange(i,j)

class NumArray:
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums
         self.step = 20
         self.cache = [0] * math.ceil(len(nums)/self.step)
         for i in range(len(nums)):
             self.cache[i//self.step] += nums[i]
 
     def update(self, i, val):
         """
         :type i: int
         :type val: int
         :rtype: void
         """
         old = self.nums[i]
         self.nums[i] = val
         self.cache[i//self.step] += (val - old)
         
     def sumRange(self, i, j):
         """
         :type i: int
         :type j: int
         :rtype: int
         """
         if (j//self.step - i//self.step) > 1:     
             spliti = ((i//self.step) + 1) * self.step - 1
             
             splitj = ((j//self.step)) * self.step
             
             sumi = sum(self.nums[i:(spliti+1)])
             sumj = sum(self.nums[splitj:(j+1)])
             sumbetween = sum(self.cache[((i//self.step) +1):((j//self.step))])
             return sumi + sumj + sumbetween
         else:
             return sum(self.nums[i:(j+1)])
 
         
 
 
 # Your NumArray object will be instantiated and called as such:
 # obj = NumArray(nums)
 # obj.update(i,val)
 # param_2 = obj.sumRange(i,j)


class NumArray:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         l = len(nums)
         self.nums = nums
         self.bit = [0] * (l+1)
         for i in range(1, l+1):
             self.update_delta(i, nums[i-1])
 
     def update(self, i, val):
         """
         :type i: int
         :type val: int
         :rtype: void
         """
         bit = self.bit
         delta = val - self.nums[i]
         self.nums[i] = val
         self.update_delta(i+1, delta)
 
     def sumRange(self, i, j):
         """
         :type i: int
         :type j: int
         :rtype: int
         """
         return self.get_sum(j+1) - self.get_sum(i)
     
     def get_sum(self, i):
         bit = self.bit
         res = 0
         while i > 0:
             res += bit[i]
             i -= (i & -i)
         
         return res
     
     def update_delta(self, i, delta):
         bit = self.bit
         l = len(bit)
         while i < l:
             bit[i] += delta
             i += (i & -i)
             
         
 
 
 # Your NumArray object will be instantiated and called as such:
 # obj = NumArray(nums)
 # obj.update(i,val)
 # param_2 = obj.sumRange(i,j)


class NumArray:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.segTree = [0 for _ in range(len(nums) * 2)]
         self.build(nums)
         self.n = len(nums)
         
     def build(self, nums):
         n = len(nums)
         self.segTree[n: 2 * n] = nums[:]
         for i in range(n - 1, 0, -1):
             self.segTree[i] = self.eval(self.segTree[2 * i], self.segTree[2 * i + 1])
             
     def eval(self, x1, x2):
         return x1 + x2
 
     def update(self, i, val):
         """
         :type i: int
         :type val: int
         :rtype: void
         """
         k = i + self.n
         delta = val - self.segTree[k]
         while k > 0:
             self.segTree[k] += delta
             k //= 2
         
 
     def sumRange(self, i, j):
         """
         :type i: int
         :type j: int
         :rtype: int
         """
         l = i + self.n
         r = j + self.n 
         s = 0
         while l <= r:
             if l & 1 == 1:
                 s += self.segTree[l]
                 l += 1
             if r & 1 == 0:
                 s += self.segTree[r]
                 
             r -= 1
             l >>= 1
             r >>= 1
         return s
         
 
 
 # Your NumArray object will be instantiated and called as such:
 # obj = NumArray(nums)
 # obj.update(i,val)
 # param_2 = obj.sumRange(i,j)