307: Space 98.30%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\n- The NumArray class is initialized with the input array nums. In the i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n- The NumArray class is initialized with the input array nums. In the __init__ method, we initialize a binary tree (segment tree) to store the range sum queries for the array.\n- The buildTree method is used to build the binary tree. We fill the leaves of the tree with the values from the input array nums, and then we fill the non-leaf nodes of the tree with the sum of their children. The binary tree is represented as a list, where the left child of node i is at index 2*i, and the right child of node i is at index 2*i+1.\n- The update method is used to update the value of an element in the input array nums. We update the corresponding leaf node in the binary tree with the new value, and then propagate the change up the tree by updating the parent nodes recursively.\n- The sumRange method is used to calculate the sum of the elements in the input array nums between two indices left and right inclusive. We first find the corresponding range in the binary tree by adding n to left and right, where n is the length of the input array nums. We then traverse the binary tree from the bottom up, adding the values of nodes that overlap with the range [left+n, right+n] to the result res.\n\n# Complexity\n- Time complexity:\n79.58%\n\n- Space complexity:\n98.30%\n\n# Code\n```\nclass NumArray:\n    def __init__(self, nums: List[int]):\n        self.n = len(nums)\n        self.tree = [0] * (2 * self.n)\n        self.buildTree(nums)\n\n    def buildTree(self, nums: List[int]) -> None:\n        # Fill leaves of the tree with nums values\n        for i in range(self.n, 2 * self.n):\n            self.tree[i] = nums[i - self.n]\n\n        # Fill non-leaf nodes of the tree with the sum of their children\n        for i in range(self.n - 1, 0, -1):\n            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]\n\n    def update(self, index: int, val: int) -> None:\n        # Update the corresponding leaf node\n        index += self.n\n        self.tree[index] = val\n\n        # Propagate the change up the tree\n        while index > 0:\n            left = right = index\n            if index % 2 == 0:\n                right = index + 1\n            else:\n                left = index - 1\n            self.tree[index // 2] = self.tree[left] + self.tree[right]\n            index //= 2\n\n    def sumRange(self, left: int, right: int) -> int:\n        # Find the sum in the range [left+n, right+n] in the tree\n        left += self.n\n        right += self.n\n        res = 0\n        while left <= right:\n            if left % 2 == 1:\n                res += self.tree[left]\n                left += 1\n            if right % 2 == 0:\n                res += self.tree[right]\n                right -= 1\n            left //= 2\n            right //= 2\n        return res\n\n```
['Array', 'Design', 'Segment Tree', 'Python', 'Python3']