# Python solution with detailed explanation

• 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):
"""
: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
``````

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