Python Elegant & Short | log(n) for sum | Binary Indexed/Fenwick Tree
\nclass BITTree:\n    """\n    Implementation of Binary Indexed Tree/Fenwick Tree\n\n    Memory:\n        creation - O(n)\n        update   - O(1)\n        get_
```\nclass BITTree:\n    """\n    Implementation of Binary Indexed Tree/Fenwick Tree\n\n    Memory:\n        creation - O(n)\n        update   - O(1)\n        get_sum  - O(1)\n\n    Time:\n        creation - O(n*log(n))\n        update   - O(log(n))\n        get_sum  - O(log(n))\n    """\n\n    def __init__(self, nums: List[int]):\n        self.bi_tree = [0] * (len(nums) + 1)\n        self.n = len(nums)\n        for i in range(self.n):\n            self.update(i + 1, nums[i])\n\n    def update(self, index: int, value: int):\n        while index <= self.n:\n            self.bi_tree[index] += value\n            index += self.low_bit(index)\n\n    def get_sum(self, index: int) -> int:\n        prefix = 0\n        while index > 0:\n            prefix += self.bi_tree[index]\n            index -= self.low_bit(index)\n        return prefix\n\n    @staticmethod\n    def low_bit(bit: int) -> int:\n        return bit & -bit\n\n\nclass NumArray:\n    """\n    Time:   O(n*log(n)) + O(log(n))\n    Memory: O(n)\n    """\n\n    def __init__(self, nums: List[int]):\n        self.nums = nums\n        self.bi_tree = BITTree(nums)\n\n    def update(self, i: int, val: int):\n        self.bi_tree.update(i + 1, val - self.nums[i])\n        self.nums[i] = val\n\n    def sumRange(self, left: int, right: int) -> int:\n        return self.bi_tree.get_sum(right + 1) - self.bi_tree.get_sum(left)\n```\n\nIf you like this solution remember to **upvote it** to let me know.\n
['Tree', 'Binary Tree', 'Python', 'Python3']