###### tags: `Leetcode` `medium` `design` `python`

# 307. Range Sum Query - Mutable

## [題目來源:] https://leetcode.com/problems/range-sum-query-mutable/

## 題目:
Given an integer array nums, handle multiple queries of the following types:

1. Update the value of an element in nums.
1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:
* NumArray(int[] nums) Initializes the object with the integer array nums.
* void update(int index, int val) Updates the value of nums[index] to be val.
* int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).


#### [圖片來源] https://leetcode.com/problems/range-sum-query-mutable/

## 解題想法:
給一個數組，可以求任意範圍內所有元素之和，且數組元素可以更改。
sumRange累加: s[left]~s[right]
update(位置,新的值)

* 使用Segment Tree_[線段樹]:
* 可視為加了額外訊息的滿二元樹
* 建樹:O(N)
* 單點修改、區間查詢:O(logN)
* 相關介紹
* https://www.jianshu.com/p/91f2c503e62f
* https://www.cnblogs.com/grandyang/p/4985506.html

關於建樹: nums=[1,3,5,7]
則: 中括號表是區域範圍，下方數字為區間和

           [0, 3]
             16
       /            \
    [0, 1]        [2, 3]
      4             12
   /     \       /      \
[0, 0] [1, 1]  [2, 2] [3, 3]
   1      3      5       7

可以用一維數組表示tree:
* nums=[1,3,5,7], tree=2*len(nums)
* 原nums元素放在leaf:最後面
* tree=[-,-,-,-,1,3,5,7]
* for i in range(len(nums)-1; -1; -1):
* tree[i]=tree[2 * i]+tree[2 * i +1]
* tree=[-,-,-, **12** , 1 , 3 , **5** , **7**]
* 依序填入後:
* tree=[-,-, 4,12,1,3,5,7]
* tree=[-,16,4,12,1,3,5,7]
* p.s: tree[0]沒啥用

### **Update(index,val)**: O(logN)
* nums=[1,3,5,7] 若想將5換成2: Update(2,2)
tree=[-,16,4,12,1,3,**2**,7]
**更新父節點**: 即tree[i // 2]
tree=[-,16,4,**9**,1,3,2,7]
tree=[-,**13**,4,9,1,3,2,7]
tree=[13,**13**,4,9,1,3,2,7] (tree[0]會更動但不用使用)

### **SumRange(left,right)**: O(logN)
* nums=[1,3,2,7]，若求**sumRange(i=1,j=3)**=12
* 對於tree=[13,13,4,9,1,3,2,7]
* 座標轉換
* new_i= **1**+len(nums)=**4**
* new_j= **3**+len(nums)=**7**
* 技巧: 判斷new_i,new_j
* 要求**向內收斂**
* **new_i要為奇數**: 右子節點,才能累加tree[new_i]
* **new_j要為偶數**: 左子節點,才能累加tree[new_j

## Python:

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.n=len(nums)
        self.tree=[0]*(2*self.n) #樹長為2n
        for pos,val in enumerate(nums):
            #原nums元素放入leaf最後一層
            self.tree[pos+self.n]=val
        #建樹:O(n)
        for i in range(self.n-1,-1,-1):
            self.tree[i]=self.tree[i*2]+self.tree[i*2+1]
            

    def update(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        new_pos=index+self.n #實際leaf的位置
        self.tree[new_pos]=val
        root=new_pos//2
        #更新父節點
        while root:
            self.tree[root]=self.tree[root*2]+self.tree[root*2+1]
            root//=2

    def sumRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        res=0
        new_i=left+self.n
        new_j=right+self.n
        while new_i<=new_j:
            #向內收斂
            if new_i%2==1:
                res+=self.tree[new_i]
                new_i+=1
            if new_j%2==0:
                res+=self.tree[new_j]
                new_j-=1
            new_i//=2
            new_j//=2
        return res

result=NumArray(nums=[1,3,5,7])
r1=result.sumRange(0,2)
print(r1)

result.update(2,2)
r2=result.sumRange(1,3)
print(r2)