🚀 Segment Tree || Iterative & Recursive || 2 approaches Template code || Python concise code 🔥🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is very good problem to start learning Segment Tree - a very powerful data structu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is very good problem to start learning Segment Tree - a very powerful data structure to make interviewer impressive \n(I think a lot of interviewer even don\'t know this data structure).\n\nI prepared 2 ways for implementing segement tree:\n1. Iterative implementation (with array)\n2. Recursive implementation (with tree)\n\nFor me, I found the 2nd way (recursive) is more intuiative and give me exactly how the tree should be, instead of using some magic numbers like in Iterative way. But I believed that the first way will be faster and more effecient.\n\n# Approach 1: Iterative Implementation\n<!-- Describe your approach to solving the problem. -->\nSegment Tree (**iterative** implementation)\n# Complexity\n- __init__: O(n) O(n)\n- **update**:   O(log(n))\n- **sumRange**: O(log(n))\n\n# Code\n```Python\nclass NumArray:\n    def __init__(self, nums: List[int]):\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 range(self.n-1, 0, -1):\n            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]\n        print(self.tree)\n\n    def update(self, index: int, val: int) -> None:\n        index += self.n\n        self.tree[index] = val\n        while index > 1:\n            self.tree[index//2] = self.tree[index] + self.tree[index^1]\n            index //= 2\n\n    def sumRange(self, left: int, right: int) -> int:\n        left += self.n\n        right += self.n\n        res = 0\n        while left <= right:\n            if left & 1:\n                # if left odd:\n                res += self.tree[left]\n                left += 1\n            if right & 1 ==0:\n                # if right even\n                res += self.tree[right]\n                right -= 1\n            left //= 2\n            right //= 2\n        return res        \n\n```\n\n# Approach 2: Recursive Implementation\n<!-- Describe your approach to solving the problem. -->\nSegment Tree (**recurisve** implementation)\n# Complexity\n- __init__: O(n) O(n)\n- **update**:   O(log(n))\n- **sumRange**: O(log(n))\n\n# Code\n```Python\nclass TreeNode:\n    def __init__(self, val, start, end, left_child = None, right_child = None):\n        self.val = val     # sum of the interval belongs to this node\n        self.start = start # start of the node\'s interval\n        self.end = end     # end of the node\'s interval\n        self.left_child = left_child   # left child node\n        self.right_child = right_child # right child node\n\nclass SegmentTree:\n    def __init__(self, nums):\n        self.nums = nums\n        self.root = self.build(0, len(nums) - 1)\n    \n    def build(self, start, end):\n        if start == end:\n            return TreeNode(self.nums[start], start, end)\n        left_child = self.build(start, (start+end)//2)\n        right_child = self.build((start+end)//2 + 1, end)\n        return TreeNode(left_child.val + right_child.val, start, end, left_child, right_child)\n    \n    def update(self, root, index, value):\n        if root.start == root.end and index == root.start: # target\n            root.val = value\n            return value\n        if root.start > index or root.end < index:\n            return root.val\n        root.val = self.update(root.left_child, index, value) + self.update(root.right_child, index, value)\n        return root.val\n\n    def query(self, root, left, right):\n        if root.start > right or root.end < left: return 0\n        if root.start >= left and root.end <= right: return root.val\n        return self.query(root.left_child, left, right) + self.query(root.right_child, left, right)\n\nclass NumArray:\n    def __init__(self, nums: List[int]):\n        self.tree = SegmentTree(nums)\n        self.root = self.tree.root\n\n    def update(self, index: int, val: int) -> None:\n        self.tree.update(self.root, index, val)\n\n    def sumRange(self, left: int, right: int) -> int:\n        return self.tree.query(self.root, left, right)\n\n\n```\n\nMy code is clean and can be re-used as a Python template for other problems.\nI hope you learned Segment Tree after this problem.\nPlease upvote if it helped you. Thank you\n\n![upvote.jfif](https://assets.leetcode.com/users/images/a2a84c9b-eaa4-4b8c-bc72-fb9787f1e750_1720094335.4607024.jpeg)\n\n\n\n
['Segment Tree', 'Python3']