# 307-range-sum-query-mutable


Try it on <a href='https://leetcode.com/problems/307-range-sum-query-mutable'>leetcode</a>

## Description
<div class="description">
<div><p>Given an integer array <code>nums</code>, handle multiple queries of the following types:</p>

<ol>
	<li><strong>Update</strong> the value of an element in <code>nums</code>.</li>
	<li>Calculate the <strong>sum</strong> of the elements of <code>nums</code> between indices <code>left</code> and <code>right</code> <strong>inclusive</strong> where <code>left &lt;= right</code>.</li>
</ol>

<p>Implement the <code>NumArray</code> class:</p>

<ul>
	<li><code>NumArray(int[] nums)</code> Initializes the object with the integer array <code>nums</code>.</li>
	<li><code>void update(int index, int val)</code> <strong>Updates</strong> the value of <code>nums[index]</code> to be <code>val</code>.</li>
	<li><code>int sumRange(int left, int right)</code> Returns the <strong>sum</strong> of the elements of <code>nums</code> between indices <code>left</code> and <code>right</code> <strong>inclusive</strong> (i.e. <code>nums[left] + nums[left + 1] + ... + nums[right]</code>).</li>
</ul>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

<pre><strong>Input</strong>
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
<strong>Output</strong>
[null, 9, null, 8]

<strong>Explanation</strong>
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>
	<li><code>0 &lt;= index &lt; nums.length</code></li>
	<li><code>-100 &lt;= val &lt;= 100</code></li>
	<li><code>0 &lt;= left &lt;= right &lt; nums.length</code></li>
	<li>At most <code>3 * 10<sup>4</sup></code> calls will be made to <code>update</code> and <code>sumRange</code>.</li>
</ul>
</div>
</div>

## Solution(Python)
```Python
class NumArray:

    def __init__(self, nums: List[int]):
        self.ds = Bits(nums)

    def update(self, index: int, val: int) -> None:
        self.ds.update(index, val)

    def sumRange(self, left: int, right: int) -> int:
        return self.ds.sumRange(left, right)


        
class NaiveNumArray:
    # Time Complexity: O(n)
    def __init__(self, nums: List[int]):
        self.nums = nums

    # Time Complexity: O(1)
    def update(self, index: int, val: int) -> None:
        self.nums[index] = val 
        
    # Time Complexity: O(n)
    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left: right+1])
    

        
class PresumNumArray:
    # Time Complexity: O(n)
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = nums
        self.presum = [0] * (1 + self.n)
        self.build()

        
    def build(self):
        for i in range(self.n):
            self.presum[i+1] += self.presum[i] + self.nums[i]

    # Time Complexity: O(n)
    def update(self, index: int, val: int) -> None:
        diff  = val - self.nums[index]
        for i in range(index + 1, self.n):
            self.presum[i+1] +=  diff
        self.nums[index] = val
        
    # Time Complexity: O(1)
    def sumRange(self, left: int, right: int) -> int:
        if left == right:
            return self.nums[left]
        return self.presum[right + 1] -  self.presum[left]
    

    
class SegmentTree:
    # Time Complexity: O(n)
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = [0] * (2*self.n)
        self.build(nums)

        
    def build(self, nums):
        i = self.n
        j = 0
        while i< 2*self.n:
            self.tree[i] = nums[j]
            i += 1
            j += 1
        for i in range(self.n - 1, -1 ,-1):
            self.tree[i] = self.tree[i*2] + self.tree[i*2 + 1]

    # Time Complexity: O(log(n))
    def update(self, index: int, val: int) -> None:
        index += self.n
        self.tree[index] = val
        while index > 0:
            left = index
            right = index
            if index % 2 == 0:
                right = index + 1
            else:
                left = index - 1
            self.tree[index//2] = self.tree[left] + self.tree[right]
            index //= 2
    # Time Complexity: O(log(n))
    def sumRange(self, left: int, right: int) -> int:
        left += self.n
        right += self.n
        
        s = 0
        while left <= right:
            if left %2 == 1:
                s += self.tree[left]
                left += 1
            if right % 2 == 0:
                s += self.tree[right]
                right -= 1
            left //=2 
            right //=2
        return s

class Bits:
    # Time Complexity: O(nlogn)
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.n = len(nums)
        self.tree = [0]*(self.n+1)
        for i in range(self.n):
            self.build(i, nums[i])
            
    def build(self, i, val):
        i += 1
        while i<=self.n:
            self.tree[i] += val
            i += i & (-i)
    # Time Complexity: O(log(n))
    def update(self, index: int, val: int) -> None:
        diff = val - self.nums[index]
        self.nums[index] = val
        self.build(index, diff)

    # Time Complexity: O(log(n))
    def sumRange(self, left: int, right: int) -> int:
        return self.sum(right) - self.sum(left-1)
    
    def sum(self, i):
        s = 0
        i += 1
        while i>0:
            s += self.tree[i]
            i -= i & (-i)
        return s


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)
```