Segment Tree Implementation and explanation | With image
This is a hands on implementation of a segment tree.\n\nFor more theory, refer to this article: https://leetcode.com/articles/a-recursive-approach-to-segment-tr
This is a hands on implementation of a segment tree.\n\nFor more theory, refer to this article: https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/\n\nYou can refer to this implementation as a "template" for a segment tree.\n\n<hr />\n\nThe idea of a segment tree is to query a range/interval in time complexity of `logn`.\n\nAlso updating a value in the tree takes `logn` time.\n\nThe other approaches to this problem would be to update in O(1) and get the query in O(n), or update in O(n) and get the query in O(1).\n\nSegment tree is the best data structure to solve the current problem with `logn` complexity for both operations.\n\n(Remember that if you have 1,000,000 elements, O(n) will scan the whole million, while `O(logn)` will scan 20 at most)\n\n# Brief introduction\nA segment tree is a binary tree that stores information about intervals. \n\nThe information we want to store in this problem is the interval sum.\n\n![image](https://assets.leetcode.com/users/images/ed7481fe-0bdf-42f4-92da-8ff4f40c3a97_1659260058.945849.png)\n\n**Query**\nWhenever we query a range, we have 3 possiblities:\n\n1. The query range (interval we query) is fully contained within the current tree interval - return the current interval sum. For example query `[0:3] -> 14`\n2. The query range is partially contained, then we do a divide and conquer to left and right subtrees. For example `[1:2]`\n3. The query range is not contained in the interval - return 0. For example you ask for `[3:3]` in the `[0:1]` part of the segment tree\n\n**Update**\nTo update the segment tree, we find the `leaf index` of the element in the tree, make the update, and update all it\'s parents until the root (including)\n\n# Implementation details\n1. Instead of building a tree, we will mimick the tree with an array. \n**Left** child will be `index*2+1` and **right** child will be `index*2+2`\n\n2. We want to have a complete binary tree, therefore we buffer the array of `nums` until it has `2^n` elements, where n is the closest power of 2.\n\n3. The segment tree will have 2^(n+1) - 1 elements. Since we need to store all the intermediary levels.\n\n4. In the update operation, we simply add the delta instead of the value.\nIf the value was 5 and now we update to 8, the `delta=3` so we add that delta to the leaf node and all parent nodes of that leaf.\n\n# Code\n```\nclass SegmentTree:\n    def __init__(self, nums: list[int]):\n        n = len(nums)\n        \n        self.buffered_nums = [*nums]\n        close_2_power = math.ceil(math.log2(n))\n        \n        # Buffer the array to be a power of 2\n        self.buffered_nums += [0] * (2**close_2_power - n)\n        \n        self.close_2_power = close_2_power\n        \n        # The tree will have 2^n+1 - 1 elements.\n        self.tree = [0] * ((2**(close_2_power + 1))-1)\n        self.init_tree(0, 0, len(self.buffered_nums) - 1)\n        \n    def init_tree(self, tree_index: int, left: int, right: int):\n        # If we found the leaf node, update the tree\n        if left == right:\n            self.tree[tree_index] = self.buffered_nums[left]\n            return\n        \n        mid = left + (right - left) // 2\n        left_child_index = tree_index * 2 + 1\n        right_child_index = tree_index * 2 + 2\n        \n        self.init_tree(left_child_index, left, mid)\n        self.init_tree(right_child_index, mid + 1, right)\n        \n        # Update segment tree level\n        self.tree[tree_index] = self.tree[left_child_index] + self.tree[right_child_index]\n    \n    def query(self, query_left: int, query_right: int):\n        return self._query(0, query_left, query_right, 0, len(self.buffered_nums) - 1)\n    \n    def _query(self, tree_index: int, query_left: int, query_right: int, interval_left: int, interval_right: int):\n        # if full contained interval\n        if interval_left >= query_left and interval_right <= query_right:\n            return self.tree[tree_index]\n        \n        # if not contained interval\n        if interval_right < query_left or interval_left > query_right:\n            return 0\n        \n        left_child_index = tree_index * 2 + 1\n        right_child_index = tree_index * 2 + 2\n        \n        # otherwise divide and conquer left and right\n        mid = interval_left + (interval_right - interval_left) // 2\n        return self._query(left_child_index, query_left, query_right, interval_left, mid) \\\n             + self._query(right_child_index, query_left, query_right, mid + 1, interval_right)\n    \n    def update(self, index: int, val: int):\n        # We know that the leaf indexes start at the 2^(k-1) - 1 and up to 2^k - 2 indexes\n        tree_index = ((2 ** self.close_2_power) - 1) + index\n        \n        delta = val - self.tree[tree_index]\n        \n\t\t# Update the leaf node and all levels up\n        while tree_index >= 0:\n            self.tree[tree_index] += delta\n\t\t\t\n\t\t\t# Parent index is (tree_index - 1) // 2\n            tree_index = (tree_index - 1) // 2\n\n\nclass NumArray:\n    def __init__(self, nums: List[int]):\n        self.segment_tree = SegmentTree(nums)\n\n    def update(self, index: int, val: int) -> None:\n        self.segment_tree.update(index, val)\n        \n    def sumRange(self, left: int, right: int) -> int:\n        return self.segment_tree.query(left, right)\n```
['Tree', 'Python']