




"""simple docstring"""





from collections.abc import Sequence
from queue import Queue



class   a__					:


			def __init__(   self   :     List[Any]   ,	UpperCamelCase_   :     Dict   ,	UpperCamelCase_   :     Any   ,	UpperCamelCase_   :     Union[str, Any]   ,	UpperCamelCase_   :     int=None   ,	UpperCamelCase_   :     Optional[Any]=None):


						"""simple docstring"""




						__UpperCAmelCase						:			int												=       start
						__UpperCAmelCase						:			Tuple												=       end
						__UpperCAmelCase						:			Optional[int]												=       val
						__UpperCAmelCase						:			Union[str, Any]												=       (start + end) // 2
						__UpperCAmelCase						:			Dict												=       left
						__UpperCAmelCase						:			str												=       right


			def __repr__(   self   :     List[str]):


						"""simple docstring"""




						return F"SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})"






class   a__					:


			def __init__(   self   :     Union[str, Any]   ,	UpperCamelCase_   :     Sequence   ,	UpperCamelCase_   :     int):


						"""simple docstring"""




						__UpperCAmelCase						:			Any												=       collection
						__UpperCAmelCase						:			Any												=       function
						if self.collection:
									__UpperCAmelCase						:			Optional[int]												=       self._build_tree(0   ,	len(_lowerCAmelCase) - 1)


			def    a_  (   self   :     Union[str, Any]   ,	UpperCamelCase_   :     Union[str, Any]   ,	UpperCamelCase_   :     Optional[Any]):


						"""simple docstring"""




						self._update_tree(self.root   ,	_lowerCAmelCase   ,	_lowerCAmelCase)


			def    a_  (   self   :     Optional[int]   ,	UpperCamelCase_   :     int   ,	UpperCamelCase_   :     List[Any]):


						"""simple docstring"""




						return self._query_range(self.root   ,	_lowerCAmelCase   ,	_lowerCAmelCase)


			def    a_  (   self   :     List[str]   ,	UpperCamelCase_   :     Optional[Any]   ,	UpperCamelCase_   :     Tuple):


						"""simple docstring"""




						if start == end:
									return SegmentTreeNode(_lowerCAmelCase   ,	_lowerCAmelCase   ,	self.collection[start])
						__UpperCAmelCase						:			int												=       (start + end) // 2
						__UpperCAmelCase						:			Dict												=       self._build_tree(_lowerCAmelCase   ,	_lowerCAmelCase)
						__UpperCAmelCase						:			List[Any]												=       self._build_tree(mid + 1   ,	_lowerCAmelCase)
						return SegmentTreeNode(_lowerCAmelCase   ,	_lowerCAmelCase   ,	self.fn(left.val   ,	right.val)   ,	_lowerCAmelCase   ,	_lowerCAmelCase)


			def    a_  (   self   :     List[str]   ,	UpperCamelCase_   :     List[Any]   ,	UpperCamelCase_   :     str   ,	UpperCamelCase_   :     List[str]):


						"""simple docstring"""




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


			def    a_  (   self   :     int   ,	UpperCamelCase_   :     Union[str, Any]   ,	UpperCamelCase_   :     List[str]   ,	UpperCamelCase_   :     int):


						"""simple docstring"""




						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   ,	_lowerCAmelCase   ,	_lowerCAmelCase)
									else:
												# range in left child tree and right child tree
												return self.fn(
												    self._query_range(node.left   ,	_lowerCAmelCase   ,	node.mid)   ,	self._query_range(node.right   ,	node.mid + 1   ,	_lowerCAmelCase)   ,	)
						else:
									# range in right child tree
									return self._query_range(node.right   ,	_lowerCAmelCase   ,	_lowerCAmelCase)


			def    a_  (   self   :     Optional[int]):


						"""simple docstring"""




						if self.root is not None:
									__UpperCAmelCase						:			List[str]												=       Queue()
									queue.put(self.root)
									while not queue.empty():
												__UpperCAmelCase						:			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				=							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    UpperCAmelCase_				( __UpperCAmelCase		:      list     ,     __UpperCAmelCase		:      int     ,     __UpperCAmelCase		:      int = 0     ,     __UpperCAmelCase		:      int = 0				)   ->					int:
      SCREAMING_SNAKE_CASE_      		=     right or len(__UpperCAmelCase				) - 1
      if left > right:
            return -1
      elif list_data[left] == key:
            return left
      elif list_data[right] == key:
            return right
      else:
            return search(__UpperCAmelCase     ,     __UpperCAmelCase     ,     left + 1     ,     right - 1				)


if __name__ == "__main__":
   import doctest

   doctest.testmod()