Python: All possible methods Explained with time and space complexity.
For this problem we can have three possible solutions:\n1. Naive Solution: Store the nums array and on each update just update the nums array directly. On each 
For this problem we can have three possible solutions:\n1. Naive Solution: Store the nums array and on each update just update the nums array directly. On each query, take the sum from left to right. \n2. Caching: Maintain a prefix sum, and on each query directly return prefix[right+1] - prefix[left]. On each update, adjust the whole prefix sum array according to the update made.\n3. Segment-Tree: Prepare a segment tree, On each query, traverse the segment tree of logarithmic height and return ans. On each update, traverse the same segment tree of logarithmic height and update.\n\n![image](https://assets.leetcode.com/users/images/11ec989c-227e-40bc-8b44-e5c2894acf73_1624007522.0668354.png)\n\nWhen to use the naive Approach: when Q <<< U (Here a <<< b means a is much lesser than b).\nWhen to use the Caching Approach: when U <<< Q.\nAnd Segment tree can be used, when U ===  Q (here a === b means a is nearly equal to b and both are high values).\n\nCode for naive Approach:\n```\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.n = len(nums)\n        self.nums = nums\n                \n    def update(self, index: int, val: int) -> None:\n        self.nums[index] = val\n\n    def sumRange(self, left: int, right: int) -> int:\n        ans = 0\n        for i in range(left,right+1):\n            ans += self.nums[i]\n        return ans\n```\n\nCode for Caching Approach:\n```\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.nums = nums\n\t\t\n\t\t# create a prefix sum array \n\t\t# if nums = [2,1,3], then prefix = [0, 2, 3, 6]\n\t\t\n        self.prefix = [0]\n        for i in nums:\n            self.prefix.append(self.prefix[-1] + i)\n        self.n = len(self.prefix)\n        \n    def update(self, index: int, val: int) -> None:\n\t\t# get the difference between the previous value and the current update value\n\t\t# it is used to add this difference to the prefix sum array\n        diff = val - self.nums[index]\n\t\t\n\t\t# aslo update the nums array as next time when this element will be updated, we dont want to\n\t\t# get the difference from the initial value of nums but from the latest updated value\n        self.nums[index] = val\n\t\t\n\t\t# adjust the prefix sum\n        for i in range(index+1, self.n):\n            self.prefix[i] += diff\n\n    def sumRange(self, left: int, right: int) -> int:\n        return self.prefix[right+1] - self.prefix[left]\n```\n\nNow, The big Boss -> **The Recursive Segment Tree Approach**: (Don\'t worry, It is not that difficult xD).\n\nBuilding the initial Segment Tree: \n![image](https://assets.leetcode.com/users/images/b971b66c-e129-4ea4-ac36-937f574f9220_1624009750.6255617.png)\n\nUpdation:\n![image](https://assets.leetcode.com/users/images/49182ee2-4368-4b4a-b401-22ade2bfb58f_1624010632.2945564.png)\n\nQuerying:\n![image](https://assets.leetcode.com/users/images/62adb12f-d9cf-4e4c-bd8d-5b8c0a93972c_1624011230.3556821.png)\n\n\nThe Full Recursive Segment Tree Code:\n```\nclass NumArray:\n\n    def __init__(self, nums: List[int]):\n        self.n = len(nums)\n        self.seg_tree = [dict() for _ in range(4*self.n)]\n        \n        def build(i, j, indx):\n            self.seg_tree[indx][\'left\'] = i\n            self.seg_tree[indx][\'right\'] = j\n            \n            if i == j:\n                self.seg_tree[indx][\'val\'] = nums[i]\n                return\n            \n            mid = (i+j)//2\n            \n            build(i, mid, 2*indx)\n            build(mid+1, j, 2*indx+1)\n            \n            self.seg_tree[indx][\'val\'] =  self.seg_tree[2*indx][\'val\'] +self.seg_tree[2*indx+1][\'val\']\n        \n        build(0,self.n-1,1) # start the tree from index 1\n        \n        \n                \n    def update(self, index: int, val: int) -> None:\n        \n        def seg_update(index, val, indx):\n            i = self.seg_tree[indx][\'left\']\n            j = self.seg_tree[indx][\'right\']\n            \n            if i==j and i==index:\n                self.seg_tree[indx][\'val\'] = val\n                return\n            \n            mid = (i+j)//2\n            \n            if index<=mid:\n                seg_update(index,val,2*indx)\n                self.seg_tree[indx][\'val\'] =  self.seg_tree[2*indx][\'val\'] +self.seg_tree[2*indx+1][\'val\']\n            else:\n                seg_update(index,val,2*indx+1)\n                self.seg_tree[indx][\'val\'] =  self.seg_tree[2*indx][\'val\'] +self.seg_tree[2*indx+1][\'val\']\n        \n        seg_update(index, val, 1)\n        \n\n    def sumRange(self, left: int, right: int) -> int:\n        \n        def query(left, right, indx):\n            i = self.seg_tree[indx][\'left\']\n            j = self.seg_tree[indx][\'right\']\n            \n            if i == left and j == right:\n                return self.seg_tree[indx][\'val\']\n            \n            mid = (i+j)//2\n            \n            if i <= left and right <=mid:\n                return query(left,right,2*indx)\n            if mid+1<=left and right <= j:\n                return query(left,right,2*indx+1)\n            \n            lval = query(left, mid, 2*indx)\n            rval = query(mid+1, right, 2*indx+1)\n            \n            return lval + rval\n        \n        return query(left, right, 1)\n```\n\nTime Complexity is given in the above table at the top of this post.\nSpace complexity: \n1. For naive approach: O(n) for storing the nums permanently in an array.\n2. For Caching Approach: O(n) for creating the prefix sum array.\n3. For Segment Tree Approach: O(4 * n) = O(n) for creating the segment tree list/array.\n(It is a 2 dimentional list but the inner dimension is always constant to 3.)\n\nHope it helps!\n
['Tree', 'Python']