Short Python
1, Segment Tree\nAn intuitive way to solve this kind of question, AC in 252ms.\npython\nclass Node:\n    def __init__(self, start, end, total = 0):\n        sel
## 1, Segment Tree\nAn intuitive way to solve this kind of question, **AC in 252ms.**\n```python\nclass Node:\n    def __init__(self, start, end, total = 0):\n        self.start  = start\n        self.end    = end\n        self.total  = total\n        self.left   = None\n        self.right  = None\n\nclass NumArray:\n    def __init__(self, nums):\n        def createNode(l, r):\n            if l > r: return None\n            if l == r: return Node(l, r, nums[l])\n            node, mid = Node(l, r), (l + r) // 2\n            node.left   = createNode(l, mid)\n            node.right  = createNode(mid + 1, r)\n            node.total  = node.left.total + node.right.total\n            return node\n        self.root = createNode(0, len(nums) - 1)\n\n    def update(self, i, val):\n        def updTotal(node, i, val):\n            if node.start == node.end:\n                node.total = val\n            else:\n                mid = (node.start + node.end) // 2\n                updTotal((node.left, node.right)[i > mid], i, val)\n                node.total = node.left.total + node.right.total\n            return node.total\n        return updTotal(self.root, i, val)\n\n    def sumRange(self, i, j):\n        def rangeSum(root, l, r):\n            if root.start == l and root.end == r: return root.total\n            mid = (root.start + root.end) // 2\n            if r <= mid:     return rangeSum(root.left,  l, r)\n            if l >= mid + 1: return rangeSum(root.right, l, r)\n            return rangeSum(root.left, l, mid) + rangeSum(root.right, mid + 1, r)\n        return rangeSum(self.root, i, j)\n```\n\n## 2, Binary Index Tree\nSame complexity but less code, please watch [this video](https://youtu.be/CWDQJGaN1gY) for more explaination of BIT. **AC in 100ms**\n```python\nclass NumArray:\n    def __init__(self, nums):\n        self.arr = [0] * len(nums)\n        self.BIT = [0] * (len(nums) + 1)\n        for i, n in enumerate(nums): self.update(i, n)\n        self.sumRange = lambda i, j: self.Sum(j + 1) - self.Sum(i)\n\n    def update(self, i, val):\n        diff, self.arr[i] = val - self.arr[i], val\n        i += 1\n        while i < len(self.BIT):\n            self.BIT[i] += diff\n            i += (i & -i)\n\n    def Sum(self, k):\n        res = 0\n        while k:\n            res += self.BIT[k]\n            k -= (k & -k)\n        return res\n```
[]