



from collections.abc import Sequence
from queue import Queue



class  lowerCamelCase__    :




		'''simple docstring'''



		def __init__(self	,__lowerCamelCase	,__lowerCamelCase	,__lowerCamelCase	,__lowerCamelCase=None	,__lowerCamelCase=None				)  ->    Union[str, Any]:

						"""simple docstring"""






						lowerCAmelCase__  :       Tuple				=  start
						lowerCAmelCase__  :       Union[str, Any]				=  end
						lowerCAmelCase__  :       List[str]				=  val
						lowerCAmelCase__  :       List[str]				=  (start + end) // 2
						lowerCAmelCase__  :       List[str]				=  left
						lowerCAmelCase__  :       List[Any]				=  right



		def __repr__(self				)  ->    List[str]:

						"""simple docstring"""






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



class  lowerCamelCase__    :




		'''simple docstring'''



		def __init__(self	,__lowerCamelCase	,__lowerCamelCase				)  ->    str:

						"""simple docstring"""






						lowerCAmelCase__  :       List[Any]				=  collection
						lowerCAmelCase__  :       Optional[int]				=  function
						if self.collection:
										lowerCAmelCase__  :       Union[str, Any]				=  self._build_tree(0	,len(UpperCAmelCase_				) - 1				)



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase				)  ->    Dict:

						"""simple docstring"""






						self._update_tree(self.root	,UpperCAmelCase_	,UpperCAmelCase_				)



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase				)  ->    List[Any]:

						"""simple docstring"""






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



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase				)  ->    Optional[int]:

						"""simple docstring"""






						if start == end:
										return SegmentTreeNode(UpperCAmelCase_	,UpperCAmelCase_	,self.collection[start]				)
						lowerCAmelCase__  :       str				=  (start + end) // 2
						lowerCAmelCase__  :       List[Any]				=  self._build_tree(UpperCAmelCase_	,UpperCAmelCase_				)
						lowerCAmelCase__  :       Any				=  self._build_tree(mid + 1	,UpperCAmelCase_				)
						return SegmentTreeNode(UpperCAmelCase_	,UpperCAmelCase_	,self.fn(left.val	,right.val				)	,UpperCAmelCase_	,UpperCAmelCase_				)



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase	,__lowerCamelCase				)  ->    Union[str, Any]:

						"""simple docstring"""






						if node.start == i and node.end == i:
										lowerCAmelCase__  :       Union[str, Any]				=  val
										return
						if i <= node.mid:
										self._update_tree(node.left	,UpperCAmelCase_	,UpperCAmelCase_				)
						else:
										self._update_tree(node.right	,UpperCAmelCase_	,UpperCAmelCase_				)
						lowerCAmelCase__  :       Tuple				=  self.fn(node.left.val	,node.right.val				)



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase	,__lowerCamelCase				)  ->    str:

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



		def 	lowerCAmelCase__   (self				)  ->    int:

						"""simple docstring"""






						if self.root is not None:
										lowerCAmelCase__  :       Tuple				=  Queue()
										queue.put(self.root				)
										while not queue.empty():
														lowerCAmelCase__  :       Dict				=  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('*' * 5_0)
														_UpperCAmelCase       :	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__	(					lowerCamelCase_	:	int):





				'''simple docstring'''

				if not isinstance(lowerCamelCase_ ,lowerCamelCase_):
								lowerCAmelCase__  :       Dict				=  f"""Input value of [number={number}] must be an integer"""
								raise TypeError(lowerCamelCase_)

				if number < 1:
								lowerCAmelCase__  :       Any				=  f"""Input value of [number={number}] must be > 0"""
								raise ValueError(lowerCamelCase_)

				lowerCAmelCase__  :       List[str]				=  1

				for i in range(1 ,lowerCamelCase_):
								current_number *= 4 * i - 2
								current_number //= i + 1

				return current_number


if __name__ == "__main__":
							import doctest

							doctest.testmod()

