





"""simple docstring"""






from collections.abc import Sequence
from queue import Queue




class 				__lowercase			:







					'''simple docstring'''




					def __init__(						self	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase=None	,			_UpperCAmelCase=None     ):
									__a :						List[Any]			       =  start
									__a :						Tuple			       =  end
									__a :						Dict			       =  val
									__a :						List[str]			       =  (start + end) // 2
									__a :						Optional[int]			       =  left
									__a :						Union[str, Any]			       =  right







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






class 				__lowercase			:







					'''simple docstring'''




					def __init__(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									__a :						Dict			       =  collection
									__a :						Tuple			       =  function
									if self.collection:
													__a :						Optional[int]			       =  self._build_tree(0	,			len(_UpperCAmelCase     ) - 1     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									self._update_tree(self.root	,			_UpperCAmelCase	,			_UpperCAmelCase     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									return self._query_range(self.root	,			_UpperCAmelCase	,			_UpperCAmelCase     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									if start == end:
													return SegmentTreeNode(_UpperCAmelCase	,			_UpperCAmelCase	,			self.collection[start]     )
									__a :						List[Any]			       =  (start + end) // 2
									__a :						Union[str, Any]			       =  self._build_tree(_UpperCAmelCase	,			_UpperCAmelCase     )
									__a :						Tuple			       =  self._build_tree(mid + 1	,			_UpperCAmelCase     )
									return SegmentTreeNode(_UpperCAmelCase	,			_UpperCAmelCase	,			self.fn(left.val	,			right.val     )	,			_UpperCAmelCase	,			_UpperCAmelCase     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									if node.start == i and node.end == i:
													__a :						Optional[Any]			       =  val
													return
									if i <= node.mid:
													self._update_tree(node.left	,			_UpperCAmelCase	,			_UpperCAmelCase     )
									else:
													self._update_tree(node.right	,			_UpperCAmelCase	,			_UpperCAmelCase     )
									__a :						Dict			       =  self.fn(node.left.val	,			node.right.val     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									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     ):
									if self.root is not None:
													__a :						List[str]			       =  Queue()
													queue.put(self.root     )
													while not queue.empty():
																	__a :						Tuple			       =  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()






"""simple docstring"""






from dataclasses import dataclass, field
from typing import ClassVar, Dict

from ..features import Features, Value
from .base import TaskTemplate




@dataclass(frozen=_UpperCamelCase							)
class 				__lowercase			(			_UpperCamelCase							):







					'''simple docstring'''




					__lowerCAmelCase  =  field(default='''language-modeling'''   ,      metadata={'''include_in_asdict_even_if_is_default''': True}							)

					__lowerCAmelCase  =  Features({'''text''': Value('''string'''							)}							)
					__lowerCAmelCase  =  Features({}							)
					__lowerCAmelCase  =  "text"







					@property
					def  _lowerCamelCase		(						self     ):
									return {self.text_column: "text"}