I’m using square root decomposition to solve a question on LeetCode.
Here is my code:
from math import ceil, sqrt
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
self.blockSize = ceil(sqrt(len(nums)))
self.blocks = [0] * self.blockSize
for i in range(len(nums)):
self.blocks[i // self.blockSize] += nums[i]
def update(self, i: int, val: int) -> None:
oldVal = self.nums[i]
self.blocks[i // self.blockSize] += (val - oldVal)
self.nums[i] = val
def sumRange(self, i: int, j: int) -> int:
ans = 0
l = i // self.blockSize
r = j // self.blockSize
for index in range(i, (l + 1) * self.blockSize):
ans += self.nums[index]
for index in range(r * self.blockSize, j + 1):
ans += self.nums[index]
for index in range(l + 1, r):
ans += self.blocks[index]
return ans
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)
I am getting wrong answer for inputs such as:
["NumArray","sumRange","update","sumRange"]
[[[-1]],[0,0],[0,1],[0,0]]
and
["NumArray","update","sumRange","sumRange","update","sumRange"]
[[[9,-8]],[0,3],[1,1],[0,1],[1,-3],[0,1]]
I’m not sure where I’m going wrong. I’m using this video as my guide for square root decomposition.