


from collections.abc import Sequence
from queue import Queue



class        a					:





     def __init__(    self					:				Any    ,	SCREAMING_SNAKE_CASE_					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				Optional[Any]    ,	SCREAMING_SNAKE_CASE_					:				int    ,	SCREAMING_SNAKE_CASE_					:				Union[str, Any]=None    ,	SCREAMING_SNAKE_CASE_					:				List[Any]=None							):
        __lowerCamelCase:				List[str]     =	start
        __lowerCamelCase:				Optional[int]     =	end
        __lowerCamelCase:				Optional[Any]     =	val
        __lowerCamelCase:				Tuple     =	(start + end) // 2
        __lowerCamelCase:				int     =	left
        __lowerCamelCase:				Dict     =	right







     def __repr__(    self					:				Optional[Any]							):
        return F'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'



class        a					:





     def __init__(    self					:				Optional[int]    ,	SCREAMING_SNAKE_CASE_					:				Sequence    ,	SCREAMING_SNAKE_CASE_					:				Dict							):
        __lowerCamelCase:				Dict     =	collection
        __lowerCamelCase:				Union[str, Any]     =	function
        if self.collection:
           __lowerCamelCase:				Union[str, Any]     =	self._build_tree(0    ,	len(SCREAMING_SNAKE_CASE_							) - 1							)





     def  SCREAMING_SNAKE_CASE__       (    self					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				Any    ,	SCREAMING_SNAKE_CASE_					:				Any							):
        self._update_tree(self.root    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)





     def  SCREAMING_SNAKE_CASE__       (    self					:				Union[str, Any]    ,	SCREAMING_SNAKE_CASE_					:				Any    ,	SCREAMING_SNAKE_CASE_					:				Union[str, Any]							):
        return self._query_range(self.root    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)





     def  SCREAMING_SNAKE_CASE__       (    self					:				List[str]    ,	SCREAMING_SNAKE_CASE_					:				Optional[Any]    ,	SCREAMING_SNAKE_CASE_					:				Dict							):
        if start == end:
           return SegmentTreeNode(SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_    ,	self.collection[start]							)
        __lowerCamelCase:				Any     =	(start + end) // 2
        __lowerCamelCase:				List[Any]     =	self._build_tree(SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)
        __lowerCamelCase:				List[str]     =	self._build_tree(mid + 1    ,	SCREAMING_SNAKE_CASE_							)
        return SegmentTreeNode(SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_    ,	self.fn(left.val    ,	right.val							)    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)





     def  SCREAMING_SNAKE_CASE__       (    self					:				str    ,	SCREAMING_SNAKE_CASE_					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				Optional[Any]    ,	SCREAMING_SNAKE_CASE_					:				Optional[int]							):
        if node.start == i and node.end == i:
           __lowerCamelCase:				List[str]     =	val
           return
        if i <= node.mid:
           self._update_tree(node.left    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)
        else:
           self._update_tree(node.right    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)
        __lowerCamelCase:				Optional[int]     =	self.fn(node.left.val    ,	node.right.val							)





     def  SCREAMING_SNAKE_CASE__       (    self					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				Any    ,	SCREAMING_SNAKE_CASE_					:				Optional[int]							):
        if node.start == i and node.end == j:
           return node.val

        if i <= node.mid:
           if j <= node.mid:
              # range in left child tree
              return self._query_range(node.left    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)
           else:
              # range in left child tree and right child tree
              return self.fn(
                  self._query_range(node.left    ,	SCREAMING_SNAKE_CASE_    ,	node.mid							)    ,	self._query_range(node.right    ,	node.mid + 1    ,	SCREAMING_SNAKE_CASE_							)    ,	)
        else:
           # range in right child tree
           return self._query_range(node.right    ,	SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							)







     def  SCREAMING_SNAKE_CASE__       (    self					:				str							):
        if self.root is not None:
           __lowerCamelCase:				Dict     =	Queue()
           queue.put(self.root							)
           while not queue.empty():
              __lowerCamelCase:				Optional[Any]     =	queue.get()
              yield node

              if node.left is not None:
                 queue.put(node.left							)

              if node.right is not None:
                 queue.put(node.right							)


if __name__ == "__main__":
   import operator

   for fn in [operator.add, max, min]:
      print('''*''' * 50)
      _A		:				int									=       SegmentTree([2, 1, 5, 3, 4], fn)
      for node in arr.traverse():
         print(node)
      print()

      arr.update(1, 5)
      for node in arr.traverse():
         print(node)
      print()

      print(arr.query_range(3, 4))  # 7
      print(arr.query_range(2, 2))  # 5
      print(arr.query_range(1, 3))  # 13
      print()






def     __lowerCAmelCase						(							snake_case	:    int = 100 )       ->							int:
   __lowerCamelCase:				List[Any]     =	0
   __lowerCamelCase:				int     =	0
   for i in range(1						,      n + 1 ):
      sum_of_squares += i**2
      sum_of_ints += i
   return sum_of_ints**2 - sum_of_squares


if __name__ == "__main__":
   print(F"""{solution() = }""")


