class TrieNode:
     # Initialize your data structure here.
    def __init__(self):
        self.word = False
        self.children = {}
    
class Trie:
    
    def __init__(self):
        self.root = TrieNode()
    
    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = TrieNode()
            node = node.children[i]
        node.word = True
    
    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the trie.
    def search(self, word):
        node = self.root
        for i in word:
            if i not in node.children:
                return False
            node = node.children[i]
        return node.word
    
    # @param {string} prefix
    # @return {boolean}
    # Returns if there is any word in the trie
    # that starts with the given prefix.
    def startsWith(self, prefix):
        node = self.root
        for i in prefix:
            if i not in node.children:
                return False
            node = node.children[i]
        return True
            
    
    # Your Trie object will be instantiated and called as such:
    # trie = Trie()
    # trie.insert("somestring")
    # trie.search("key")

class NumArray:

    def __init__(self, nums: List[int]):
        self.arr = nums
        self.size = len(nums)
        self.sum_arr = []
        temp = 0
        for num in nums:
            temp += num
            self.sum_arr.append(temp)
        print(self.sum_arr)

    def update(self, index: int, val: int) -> None:
        if index >= len(self.arr):
            return
        gap = self.arr[index] - val 
        self.arr[index] = val
        for i in range(index, self.size):
            self.sum_arr[i] -= gap

    def sumRange(self, left: int, right: int) -> int:
        res = self.sum_arr[right]
        if left - 1 >= 0:
            res -= self.sum_arr[left - 1]
        return res


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

class NumArray:
    
    # this code implements Binary Indexed Tree
    # for fast queries and updates of sums
    
    def __init__(self, nums: List[int]):
        self.size = len(nums)
        self.nums = nums
        self.tree = [0] * (self.size + 1)
        self._build()
    
    # Binary Indexed Tree: build the tree
    def _build(self):
        for i in range(self.size):
            self._update(i, self.nums[i])
    
    # Binary Indexed Tree: update the tree
    def _update(self, i, d):
        i += 1
        while i <= self.size:
            self.tree[i] += d
            i += i & (-i)
    
    # Binary Indexed Tree: query sum for [0:i] (both ends included)
    def _query(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    # updating the tree is done by adding the difference
    # between old and new values to the respective nodes
    def update(self, i: int, v: int) -> None:
        d = v - self.nums[i]
        self.nums[i] = v
        self._update(i, d)

    # sum for the range [left:right] can be computed as the 
    # difference of sums for ranges [0:left-1] and [0:right]
    def sumRange(self, left: int, right: int) -> int:
        left_sum  = self._query(left-1) if left > 0 else 0
        right_sum = self._query(right) 
        return right_sum - left_sum