Python, sqrt buckets


  • 0
    Y
    class NumArray(object):
        def __init__(self, nums):
            if not nums:
                return
            self.nums = nums
            self.bucket_width = int(sqrt(len(nums)))
            self.nb_buckets = (len(nums) // self.bucket_width) + 1
            self.bucket_sums = [0] * self.nb_buckets
            for i in range(len(nums)):
                self.bucket_sums[i // self.bucket_width] += nums[i]
    
        def update(self, i, val):
            self.bucket_sums[i // self.bucket_width] += (val - self.nums[i])
            self.nums[i] = val
    
        def sumRange(self, i, j):
            first = (i // self.bucket_width) + 1       # first full bucket
            last = (j // self.bucket_width) - 1        # last full bucket
            
            if first > last:    # sum directly from nums array
                return sum(self.nums[i:j+1])
                
            # else sum buckets
            result = sum(self.bucket_sums[first:last+1])
            # then add from i, to but excluding the first index of the first full bucket
            result += sum(self.nums[i:first * self.bucket_width])
            # then add from the first index of the bucket after the last full bucket, to but excluding j+1
            result += sum(self.nums[(last+1) * self.bucket_width:j+1])
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.