[Python3] 4 approaches
\nApproach 1 "brute force"\n\n\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.diff = {}\n        self.nums = nums\n        self.pref
\nApproach 1 "brute force"\n\n```\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.diff = {}\n        self.nums = nums\n        self.prefix = [0]\n        for x in nums: self.prefix.append(self.prefix[-1] + x)\n\n    def update(self, i: int, val: int) -> None:\n        self.diff[i] = val - self.nums[i]\n\n    def sumRange(self, i: int, j: int) -> int:\n        ans = self.prefix[j+1] - self.prefix[i]\n        for k, v in self.diff.items():\n            if i <= k <= j: ans += v\n        return ans \n```\n\n`sqrt` buckets \n```\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        """Initialize class ~ O(sqrt(N))"""\n        self.nums = nums \n        self.n = ceil(sqrt(len(nums)))\n        self.bucket = [0]*self.n\n        for i, x in enumerate(nums):\n            self.bucket[i//self.n] += x\n        \n    def update(self, i: int, val: int) -> None:\n        """Update ith number and its corresponding bucket."""\n        self.bucket[i//self.n] += val - self.nums[i]\n        self.nums[i] = val \n\n    def sumRange(self, i: int, j: int) -> int:\n        """Retrieve sum between i and j through buckets."""\n        ii, jj = i//self.n, j//self.n\n        if ii == jj: #only one bucket \n            ans = sum(self.nums[k] for k in range(i, j+1))\n        else: \n            ans = sum(self.bucket[kk] for kk in range(ii+1, jj)) #whole buckets \n            ans += sum(self.nums[k] for k in range(i, (ii+1)*self.n)) #partial bucket (leading)\n            ans += sum(self.nums[k] for k in range(jj*self.n, j+1)) #partial bucket (trailing)\n        return ans \n```\n\nApproach 3 "segment tree"\n```\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        """Build segment tree ~ O(N)"""\n        self.n = len(nums)\n        self.tree = [0]*2*self.n\n        for i in range(self.n): \n            self.tree[i+self.n] = nums[i]\n        for i in reversed(range(self.n)):\n            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]\n\n    def update(self, i: int, val: int) -> None:\n        """Update value on segment tree ~ O(logN)"""\n        i += self.n\n        self.tree[i] = val \n        while i: \n            left, right = (i-1, i) if i%2 else (i, i+1)\n            self.tree[i//2] = self.tree[left] + self.tree[right]\n            i //= 2\n\n    def sumRange(self, i: int, j: int) -> int:\n        """Retrieve range sum on segment tree ~ O(logN)"""\n        ans = 0\n        i, j = i+self.n, j+self.n\n        while i <= j: \n            if i%2: #right child \n                ans += self.tree[i]\n                i += 1\n            if not j%2: \n                ans += self.tree[j]\n                j -= 1\n            i //= 2\n            j //= 2\n        return ans \n```\n\nA more typical setment tree implementation \n```\nclass SegTree: \n    def __init__(self, arr: List[int]): \n        self.n = len(arr)\n        self.data = [0]*(4*self.n)\n        self._build(arr, 0, 0, self.n)\n\n    def _build(self, arr: List[int], k: int, lo: int, hi: int) -> None: \n        if lo+1 == hi: \n            self.data[k] = arr[lo]\n            return \n        mid = lo + hi >> 1\n        self._build(arr, 2*k+1, lo, mid)\n        self._build(arr, 2*k+2, mid, hi)\n        self.data[k] = self.data[2*k+1] + self.data[2*k+2]\n\n    def update(self, idx: int, val: int, k: int = 0, lo: int = 0, hi: int = 0) -> None:\n        if not hi: hi = self.n\n        if lo+1 == hi: \n            self.data[k] = val \n            return \n        mid = lo + hi >> 1\n        if idx < mid: \n            self.update(idx, val, 2*k+1, lo, mid) \n        else: \n            self.update(idx, val, 2*k+2, mid, hi)\n        self.data[k] = self.data[2*k+1] + self.data[2*k+2]\n\n    def query(self, qlo: int, qhi: int, k: int = 0, lo: int = 0, hi: int = 0) -> int: \n        if not hi: hi = self.n\n        if qlo <= lo and hi <= qhi: return self.data[k] # total overlap \n        if qhi <= lo or  hi <= qlo: return 0 # no overlap \n        mid = lo + hi >> 1 # partial overlap \n        return self.query(qlo, qhi, 2*k+1, lo, mid) + self.query(qlo, qhi, 2*k+2, mid, hi)\n\n\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.tree = SegTree(nums)\n\n    def update(self, index: int, val: int) -> None:\n        self.tree.update(index, val)\n\n    def sumRange(self, left: int, right: int) -> int:\n        return self.tree.query(left, right+1)\n\n\n# Your NumArray object will be instantiated and called as such:\n# obj = NumArray(nums)\n# obj.update(index,val)\n# param_2 = obj.sumRange(left,right)\n```\n\nApproach 4 - Fenwick tree \n```\nclass Fenwick:\n    def __init__(self, n): \n        self.data = [0]*(n+1)\n    \n    def add(self, k, x): \n        k += 1\n        while k < len(self.data): \n            self.data[k] += x\n            k += k & -k \n    \n    def sum(self, k):\n        k += 1\n        ans = 0\n        while k: \n            ans += self.data[k]\n            k -= k & -k \n        return ans \n    \n\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.nums = nums\n        self.tree = Fenwick(len(nums))\n        for i, x in enumerate(nums): \n            self.tree.add(i, x)\n\n    def update(self, index: int, val: int) -> None:\n        self.tree.add(index, val - self.nums[index])\n        self.nums[index] = val \n            \n    def sumRange(self, left: int, right: int) -> int:\n        return self.tree.sum(right) - self.tree.sum(left-1)\n```
['Python3']