[link](https://leetcode.com/problems/range-sum-query-mutable/)

---

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

Update the value of an element in nums.
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]).

#### Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
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

#### Constraints:

- 1 <= nums.length <= 3 * 104
- -100 <= nums[i] <= 100
- 0 <= index < nums.length
- -100 <= val <= 100
- 0 <= left <= right < nums.length
- At most 3 * 104 calls will be made to update and sumRange.
---

Node: The Node class represents a node in a segment tree. Each node contains information about the range it represents (start and end), the sum of the values in that range (total), and pointers to its left and right child nodes (left and right).

NumArray: The NumArray class implements a segment tree to efficiently handle the update and sumRange operations on a list of numbers. It initializes by building the segment tree from the input list of numbers. The update method modifies a value at a specific index in the list and updates the corresponding segment tree node. The sumRange method calculates the sum of values within a given range using the segment tree.

Here's how the NumArray class works:

The constructor (__init__) initializes the segment tree by calling the buildTree method. The buildTree method is a recursive function that builds the segment tree by dividing the range into smaller sub-ranges and creating nodes for each sub-range. The total sum of each node's range is calculated by summing the total values of its left and right children.

The update method modifies a value at a specific index index in the input list and updates the corresponding segment tree node. The updateVal function is a recursive function that traverses down the segment tree to find the node that represents the index. Once the node is found, its total value is updated, and the function returns the updated value.

The sumRange method calculates the sum of values within a given range [left, right] using the segment tree. The rangeSum function is a recursive function that traverses down the segment tree to find the nodes that cover the given range. It returns the sum of the total values of the nodes that fully or partially overlap with the given range.

#### Solution 1

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None
    

class NumArray:

    def __init__(self, nums: List[int]):
        def buildTree(nums, L, R):
            if L > R:
                return None

            if L == R:
                n = Node(L, R)
                n.total = nums[L]
                return n    

            mid = (L + R) // 2
            root = Node(L, R)
            root.left = buildTree(nums, L, mid)
            root.right = buildTree(nums, mid + 1, R)
            root.total = root.left.total + root.right.total

            return root

        self.root = buildTree(nums, 0, len(nums) - 1)
            
        
    def update(self, index: int, val: int) -> None:
        def updateVal(root, i, val):
            if root.start == root.end:
                root.total = val
                return val

            mid = (root.start + root.end) // 2
            if index <= mid:
                updateVal(root.left, i, val)
            else:
                updateVal(root.right, i, val)
            
            root.total = root.left.total + root.right.total
            return root.total
        return updateVal(self.root, index, val)

            
    def sumRange(self, left: int, right: int) -> int:
        def rangeSum(root, l, r):
            if root.start == l and root.end == r:
                return root.total

            mid = (root.start + root.end) // 2
            if r <= mid:
                return rangeSum(root.left, l, r)
            elif l >= mid + 1:
                return rangeSum(root.right, l, r)
            else:
                return rangeSum(root.left, l ,mid) + rangeSum(root.right, mid + 1, r)
    
        return rangeSum(self.root, left, right)

The time complexity of the NumArray constructor is O(n), where n is the number of elements in the input list. The time complexity of the update and sumRange methods is O(log n) on average, due to the balanced nature of the segment tree.

he space complexity of the NumArray class is O(n), mainly due to the segment tree construction and the recursive calls in the rangeSum and updateVal methods.