


from collections.abc import Sequence
from queue import Queue
class 						lowerCamelCase_							:



					'''simple docstring'''







					def __init__(					self			,							snake_case_			,							snake_case_			,							snake_case_			,							snake_case_=None			,							snake_case_=None    ) ->      Optional[Any]:







								'''simple docstring'''

								__lowercase			       = start
								__lowercase			       = end
								__lowercase			       = val
								__lowercase			       = (start + end) // 2
								__lowercase			       = left
								__lowercase			       = right






					def __repr__(					self    ) ->      str:







								'''simple docstring'''

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




class 						lowerCamelCase_							:



					'''simple docstring'''







					def __init__(					self			,							snake_case_			,							snake_case_    ) ->      Optional[int]:







								'''simple docstring'''

								__lowercase			       = collection
								__lowercase			       = function
								if self.collection:
											__lowercase			       = self._build_tree(0			,							len(snake_case_    ) - 1    )






					def A   (					self			,							snake_case_			,							snake_case_    ) ->      Any:







								'''simple docstring'''

								self._update_tree(self.root			,							snake_case_			,							snake_case_    )






					def A   (					self			,							snake_case_			,							snake_case_    ) ->      List[str]:







								'''simple docstring'''

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






					def A   (					self			,							snake_case_			,							snake_case_    ) ->      Any:







								'''simple docstring'''

								if start == end:
											return SegmentTreeNode(snake_case_			,							snake_case_			,							self.collection[start]    )
								__lowercase			       = (start + end) // 2
								__lowercase			       = self._build_tree(snake_case_			,							snake_case_    )
								__lowercase			       = self._build_tree(mid + 1			,							snake_case_    )
								return SegmentTreeNode(snake_case_			,							snake_case_			,							self.fn(left.val			,							right.val    )			,							snake_case_			,							snake_case_    )






					def A   (					self			,							snake_case_			,							snake_case_			,							snake_case_    ) ->      Dict:







								'''simple docstring'''

								if node.start == i and node.end == i:
											__lowercase			       = val
											return
								if i <= node.mid:
											self._update_tree(node.left			,							snake_case_			,							snake_case_    )
								else:
											self._update_tree(node.right			,							snake_case_			,							snake_case_    )
								__lowercase			       = self.fn(node.left.val			,							node.right.val    )






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






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







								'''simple docstring'''

								if self.root is not None:
											__lowercase			       = Queue()
											queue.put(self.root    )
											while not queue.empty():
														__lowercase			       = 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			:			Tuple												=					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()






import copy
from dataclasses import dataclass
from pathlib import Path
from typing import Dict, Optional, Union
@dataclass
class 						lowerCamelCase_							:



					'''simple docstring'''







					__UpperCAmelCase							  =					None
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					None
					__UpperCAmelCase							  =					None
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					True
					__UpperCAmelCase							  =					None
					__UpperCAmelCase							  =					1
					__UpperCAmelCase							  =					None
					__UpperCAmelCase							  =					False
					__UpperCAmelCase							  =					None
					__UpperCAmelCase							  =					None






					def A   (					self    ) ->      "DownloadConfig":







								'''simple docstring'''

								return self.__class__(**{k: copy.deepcopy(snake_case_    ) for k, v in self.__dict__.items()}    )


