






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

  '''simple docstring'''







  def __init__(      self		:			Optional[Any]       ,				lowerCamelCase		:			Union[str, Any]       ,				lowerCamelCase		:			Optional[Any]       ,				lowerCamelCase		:			str       ,				lowerCamelCase		:			List[str]=None       ,				lowerCamelCase		:			Optional[int]=None							)						->	Tuple:


         """simple docstring"""
         _UpperCAmelCase							=    start
         _UpperCAmelCase							=    end
         _UpperCAmelCase							=    val
         _UpperCAmelCase							=    (start + end) // 2
         _UpperCAmelCase							=    left
         _UpperCAmelCase							=    right





  def __repr__(      self		:			Optional[Any]							)						->	int:


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



class 		SCREAMING_SNAKE_CASE__	:

  '''simple docstring'''







  def __init__(      self		:			Union[str, Any]       ,				lowerCamelCase		:			Sequence       ,				lowerCamelCase		:			str							)						->	Union[str, Any]:


         """simple docstring"""
         _UpperCAmelCase							=    collection
         _UpperCAmelCase							=    function
         if self.collection:
                _UpperCAmelCase							=    self._build_tree(0       ,				len(lowerCamelCase							) - 1							)


  def  lowerCamelCase       (      self		:			int       ,				lowerCamelCase		:			Optional[int]       ,				lowerCamelCase		:			List[str]							)						->	Optional[int]:


         """simple docstring"""
         self._update_tree(self.root       ,				lowerCamelCase       ,				lowerCamelCase							)


  def  lowerCamelCase       (      self		:			Any       ,				lowerCamelCase		:			List[Any]       ,				lowerCamelCase		:			Tuple							)						->	Union[str, Any]:


         """simple docstring"""
         return self._query_range(self.root       ,				lowerCamelCase       ,				lowerCamelCase							)


  def  lowerCamelCase       (      self		:			int       ,				lowerCamelCase		:			Any       ,				lowerCamelCase		:			Union[str, Any]							)						->	List[Any]:


         """simple docstring"""
         if start == end:
                return SegmentTreeNode(lowerCamelCase       ,				lowerCamelCase       ,				self.collection[start]							)
         _UpperCAmelCase							=    (start + end) // 2
         _UpperCAmelCase							=    self._build_tree(lowerCamelCase       ,				lowerCamelCase							)
         _UpperCAmelCase							=    self._build_tree(mid + 1       ,				lowerCamelCase							)
         return SegmentTreeNode(lowerCamelCase       ,				lowerCamelCase       ,				self.fn(left.val       ,				right.val							)       ,				lowerCamelCase       ,				lowerCamelCase							)


  def  lowerCamelCase       (      self		:			List[str]       ,				lowerCamelCase		:			List[Any]       ,				lowerCamelCase		:			Dict       ,				lowerCamelCase		:			int							)						->	Union[str, Any]:


         """simple docstring"""
         if node.start == i and node.end == i:
                _UpperCAmelCase							=    val
                return
         if i <= node.mid:
                self._update_tree(node.left       ,				lowerCamelCase       ,				lowerCamelCase							)
         else:
                self._update_tree(node.right       ,				lowerCamelCase       ,				lowerCamelCase							)
         _UpperCAmelCase							=    self.fn(node.left.val       ,				node.right.val							)


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





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


         """simple docstring"""
         if self.root is not None:
                _UpperCAmelCase							=    Queue()
                queue.put(self.root							)
                while not queue.empty():
                       _UpperCAmelCase							=    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:     Union[str, Any]   					=					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_mega''': ['''MEGA_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''MegaConfig''', '''MegaOnnxConfig'''],
}

try:
  if not is_torch_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  UpperCAmelCase_           =				[
      '''MEGA_PRETRAINED_MODEL_ARCHIVE_LIST''',
      '''MegaForCausalLM''',
      '''MegaForMaskedLM''',
      '''MegaForMultipleChoice''',
      '''MegaForQuestionAnswering''',
      '''MegaForSequenceClassification''',
      '''MegaForTokenClassification''',
      '''MegaModel''',
      '''MegaPreTrainedModel''',
  ]

if TYPE_CHECKING:
  from .configuration_mega import MEGA_PRETRAINED_CONFIG_ARCHIVE_MAP, MegaConfig, MegaOnnxConfig

  try:
    if not is_torch_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_mega import (
        MEGA_PRETRAINED_MODEL_ARCHIVE_LIST,
        MegaForCausalLM,
        MegaForMaskedLM,
        MegaForMultipleChoice,
        MegaForQuestionAnswering,
        MegaForSequenceClassification,
        MegaForTokenClassification,
        MegaModel,
        MegaPreTrainedModel,
    )

else:
  import sys

  UpperCAmelCase_           =				_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)