Python solution with detailed explanation


  • 0
    G

    Solution

    Range Sum Query - Mutable https://leetcode.com/problems/range-sum-query-mutable/

    Square Root Decomposition O(sqrt(N))

    from math import sqrt
    class NumArray(object):
        def __init__(self, nums):
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            self.nums, self.R = nums, int(sqrt(len(nums)))
            self.pp, c_sum = [], 0
            for idx,x in enumerate(nums):
                c_sum = c_sum + x
                if (idx+1)%self.R == 0:
                    self.pp.append(c_sum)
                    c_sum = 0
            if len(nums) and len(nums)%self.R:  #### NOTE IF INPUT IS [], THEN N IS 0. When N%self.R != 0, we will have have remaining sum.
                self.pp.append(c_sum)
            return
        
        def update(self, i, val):
            """
            :type i: int
            :type val: int
            :rtype: int
            """
            self.pp[i//self.R], self.nums[i] = self.pp[i//self.R]-self.nums[i]+val, val
    
        def sumRange(self, i, j):
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            result, b_s, b_e = 0, i//self.R, j//self.R
            # boundary condition: i == j
            if b_s == b_e:
                for k in range(i,j+1):
                    result += self.nums[k]
                return result
            # sqrt(n): intermediate blocks
            for k in range(b_s+1, b_e):
                result += self.pp[k]
            # boundary 1
            for i in range(i, (b_s+1)*self.R):
                result += self.nums[i]
            # boundary 2
            for i in range(b_e*self.R, j+1):
                result += self.nums[i]
            return result
    

Log in to reply
 

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