**Solution**

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

**Square Root Decomposition O(sqrt(N))**

- Divide N items into x chunks. Pre-process these chunks and update the sums of these chunks later. Then the cost of a query will be C = N/x + x. Here N/x is the number of chunks and x will be the cost in the boundaries. Now first order derivative set to zero gives us x = sqrt(N) for the minimal cost.
- Corner cases: input=[], i == j, i and j in same chunk.
- We can use segment tree to get the complexity down to log(N). https://leetcode.com/articles/recursive-approach-segment-trees-range-sum-queries-lazy-propagation/#recursive-methods-for-segment-trees

```
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
```