


"""simple docstring"""



import inspect
import unittest







class    __a						( unittest.TestCase							):







				def      lowerCamelCase_     ( self   ):

					'''simple docstring'''






					try:
						import diffusers  # noqa: F401
					except ImportError:
						assert False







				def      lowerCamelCase_     ( self   ):

					'''simple docstring'''






					import diffusers
					from diffusers.dependency_versions_table import deps

					lowerCAmelCase_      							=			inspect.getmembers(UpperCAmelCase      ,	inspect.isclass   )

					for cls_name, cls_module in all_classes:
						if "dummy_" in cls_module.__module__:
							for backend in cls_module._backends:
								if backend == "k_diffusion":
									lowerCAmelCase_      							=			'''k-diffusion'''
								elif backend == "invisible_watermark":
									lowerCAmelCase_      							=			'''invisible-watermark'''
								assert backend in deps, F"""{backend} is not in the deps table!"""



"""simple docstring"""



from collections.abc import Sequence
from queue import Queue







class    __a						:







				def __init__( self      ,	UpperCAmelCase      ,	UpperCAmelCase      ,	UpperCAmelCase      ,	UpperCAmelCase=None      ,	UpperCAmelCase=None   ):

					'''simple docstring'''






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







				def __repr__( self   ):

					'''simple docstring'''






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







class    __a						:







				def __init__( self      ,	UpperCAmelCase      ,	UpperCAmelCase   ):

					'''simple docstring'''






					lowerCAmelCase_      							=			collection
					lowerCAmelCase_      							=			function
					if self.collection:
						lowerCAmelCase_      							=			self._build_tree(0      ,	len(UpperCAmelCase   ) - 1   )







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase   ):

					'''simple docstring'''






					self._update_tree(self.root      ,	UpperCAmelCase      ,	UpperCAmelCase   )







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase   ):

					'''simple docstring'''






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







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase   ):

					'''simple docstring'''






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







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase      ,	UpperCAmelCase   ):

					'''simple docstring'''






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







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase      ,	UpperCAmelCase   ):

					'''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   ):

					'''simple docstring'''






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