Segment Tree
Code\n\nclass SegmentTree:\n    class Node:\n        def __init__(self, start, end):\n            self.start = start\n            self.end = end\n            se
# Code\n```\nclass SegmentTree:\n    class Node:\n        def __init__(self, start, end):\n            self.start = start\n            self.end = end\n            self.left = None\n            self.right = None\n            self.sum = 0\n    \n    def __init__(self, start, end):\n        def _build(start, end):\n            if start > end:\n                return None\n            \n            if start == end:\n                return SegmentTree.Node(start, end)\n            \n            node = SegmentTree.Node(start, end)\n            mid = (start + end) // 2\n            node.left = _build(start, mid)\n            node.right = _build(mid + 1, end)\n            return node\n        self.root = _build(start, end)\n    \n    def update(self, ind, val):\n        def _update(node):\n            if not node or node.start > ind or node.end < ind:\n                return\n            \n            if node.start == node.end == ind:\n                node.sum = val\n                return\n            \n            _update(node.left)\n            _update(node.right)\n            node.sum = node.left.sum + node.right.sum\n        _update(self.root)\n    \n    def query(self, query_start, query_end):\n        def _query(node):\n            if not node or node.start > query_end or node.end < query_start:\n                return 0\n            \n            if node.start >= query_start and node.end <= query_end:\n                return node.sum\n            \n            return _query(node.left) + _query(node.right)\n        return _query(self.root)\n\n\nclass NumArray:\n    def __init__(self, nums: List[int]):\n        self.segment_tree = SegmentTree(0, len(nums) - 1)\n        for i, num in enumerate(nums):\n            self.segment_tree.update(i, num)\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```
['Segment Tree', 'Python3']