[Python] Clean BIT template with solution, explained
There are two classical way how you can solve this problem: segment trees or binary indexed trees. The second one is easier to code. For more definition of BIT,
There are two classical way how you can solve this problem: segment trees or binary indexed trees. The second one is easier to code. For more definition of BIT, see wikipedia: https://en.wikipedia.org/wiki/Fenwick_tree\n\nHere we need not to update value by `delta` as it is done in classical implementation, but replace number. So we need to keep both BIT and original array: we keep `self.bit`: our tree and `self.nums` our nums. When we do initialization, here I do it not in optimal way: we update number by number in our `BIT`: so total complexity of initialization will be `O(n log n)` - there exists also `O(n)` way to do it, but it is more difficult to code. Inside function `update` we update both BIT and `self.nums`. Finally, to evaluate `sumRange`, we apply two times `query`: `query(x)` returns sum of first `x` elements.\n\n#### Complexity\nSpace complexity is `O(n)` for whole data structure. Time complexity of initialization is `O(n log n)`, time complexity of `update` and `sumRange` is `O(log n)`.\n\n\n#### Code\n```python\nclass BIT:\n    def __init__(self, n):\n        self.sums = [0] * (n+1)\n    \n    def update(self, i, delta):\n        while i < len(self.sums):\n            self.sums[i] += delta\n            i += i & (-i)\n    \n    def query(self, i):\n        res = 0\n        while i > 0:\n            res += self.sums[i]\n            i -= i & (-i)\n        return res\n\nclass NumArray:\n    def __init__(self, nums):\n        self.bit = BIT(len(nums))\n        for i, num in enumerate(nums):\n            self.bit.update(i+1, num)\n        self.nums = [0] + nums\n\n    def update(self, i, val):\n        self.bit.update(i+1, val - self.nums[i+1])\n        self.nums[i+1] = val\n\n    def sumRange(self, i, j):\n        return self.bit.query(j+1) - self.bit.query(i)\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Binary Indexed Tree']