Python with explanation O(1) update O(sqrt(n)) sumRange - very short
The idea is breaking the initial array into sqrt(n) sub-arrays (blocks), each of length sqrt(n). If n is not a perfect square, we will pad it with 0 so that it 
The idea is breaking the initial array into `sqrt(n)` sub-arrays (blocks), each of length `sqrt(n)`. If `n` is not a perfect square, we will pad it with 0 so that it becomes perfect square.\n- With that, an element with index `i` in the original array will be within block of index `i // blockSize`, and the offset of the corresponding element in that block is `i % blockSize`.\n- We will also maintain an array `blockSum` to store each sum of each block. \n\nGiven all of the above, for method `sumRange(left, right)`, we sum all the blocks from block that has number of index `left` (call if `leftMostBlock`) to block that has number of index `right` (call if  `rightMostBlock`), MINUS what we have over-added: the start of `leftMostBlock` to index `left`, and `rightMostBlock` from index `right + 1` to its end\n\nRun time analysis:\n- Summing all the blocks from block that has number of index `left` to block that has number of index `right` takes `O(sqrt(n))` time since there are at most `sqrt(n)` blocks to be added\n- MINUS the start of `leftMostBlock` to index `left`, and MINUS `rightMostBlock` from index `right + 1` to its end, each takes `O(sqrt(n))` time since the size of each block is at most `O(sqrt(n))`\n\n=> Overall `O(sqrt(n))` for `sumRange()`, and `O(1)` for `update()`\n```\nclass NumArray:\n    \n    # sqrt decomposition\n    def __init__(self, nums: List[int]):\n        self.nums = nums\n        self.blockSize = ceil(len(nums)**0.5)\n        self.blockSum = [0]*self.blockSize\n        for i, num in enumerate(nums):\n            self.blockSum[i//self.blockSize] += num\n                        \n    # O(1) time\n    def update(self, index: int, val: int) -> None:\n        self.blockSum[index//self.blockSize] += val - self.nums[index]\n        self.nums[index] = val\n        \n    # O(sqrt(n)) time\n    def sumRange(self, left: int, right: int) -> int:\n        idxLeft, offsetLeft = divmod(left, self.blockSize)\n        idxRight, offsetRight = divmod(right, self.blockSize)\n        return sum(self.blockSum[idxLeft: idxRight + 1])\\\n            - sum(self.nums[idxLeft*self.blockSize: idxLeft*self.blockSize + offsetLeft])\\\n            - sum(self.nums[idxRight*self.blockSize + offsetRight + 1: (idxRight + 1)*self.blockSize])\n```
['Python', 'Python3']