



from collections.abc import Sequence
from queue import Queue

class  __snake_case      :







							'''simple docstring'''






							def __init__(							self  ,  a_  ,  a_  ,  a_  ,  a_=None  ,  a_=None		):
											a__				      =		start
											a__				      =		end
											a__				      =		val
											a__				      =		(start + end) // 2
											a__				      =		left
											a__				      =		right







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




class  __snake_case      :







							'''simple docstring'''






							def __init__(							self  ,  a_  ,  a_		):
											a__				      =		collection
											a__				      =		function
											if self.collection:
															a__				      =		self._build_tree(0  ,  len(a_		) - 1		)


							def _a      (							self  ,  a_  ,  a_		):
											self._update_tree(self.root  ,  a_  ,  a_		)


							def _a      (							self  ,  a_  ,  a_		):
											return self._query_range(self.root  ,  a_  ,  a_		)


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


							def _a      (							self  ,  a_  ,  a_  ,  a_		):
											if node.start == i and node.end == i:
															a__				      =		val
															return
											if i <= node.mid:
															self._update_tree(node.left  ,  a_  ,  a_		)
											else:
															self._update_tree(node.right  ,  a_  ,  a_		)
											a__				      =		self.fn(node.left.val  ,  node.right.val		)


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







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






from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_torch_available,
)


UpperCAmelCase							 =					{
    """configuration_falcon""": ["""FALCON_PRETRAINED_CONFIG_ARCHIVE_MAP""", """FalconConfig"""],
}

try:
	if not is_torch_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	UpperCAmelCase							 =					[
	    """FALCON_PRETRAINED_MODEL_ARCHIVE_LIST""",
	    """FalconForCausalLM""",
	    """FalconModel""",
	    """FalconPreTrainedModel""",
	    """FalconForSequenceClassification""",
	    """FalconForTokenClassification""",
	    """FalconForQuestionAnswering""",
	]


if TYPE_CHECKING:
	from .configuration_falcon import FALCON_PRETRAINED_CONFIG_ARCHIVE_MAP, FalconConfig

	try:
		if not is_torch_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .modeling_falcon import (
		    FALCON_PRETRAINED_MODEL_ARCHIVE_LIST,
		    FalconForCausalLM,
		    FalconForQuestionAnswering,
		    FalconForSequenceClassification,
		    FalconForTokenClassification,
		    FalconModel,
		    FalconPreTrainedModel,
		)


else:
	import sys

	UpperCAmelCase							 =					_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)

