


from collections.abc import Sequence
from queue import Queue






class   __lowercase				:





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






         """simple docstring"""







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





      def __repr__(		self						:					int       )    ->   Any:






         """simple docstring"""







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






class   __lowercase				:





      def __init__(		self						:					str					,       __lowerCamelCase						:					Sequence					,       __lowerCamelCase						:					Optional[int]       )    ->   Tuple:






         """simple docstring"""







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





      def        _lowercase				(		self						:					Any					,       __lowerCamelCase						:					Tuple					,       __lowerCamelCase						:					Dict       )    ->   Union[str, Any]:






         """simple docstring"""







         self._update_tree(self.root					,       __lowerCamelCase					,       __lowerCamelCase       )





      def        _lowercase				(		self						:					Dict					,       __lowerCamelCase						:					Union[str, Any]					,       __lowerCamelCase						:					Any       )    ->   Tuple:






         """simple docstring"""







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





      def        _lowercase				(		self						:					int					,       __lowerCamelCase						:					str					,       __lowerCamelCase						:					List[Any]       )    ->   List[str]:






         """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        _lowercase				(		self						:					Any					,       __lowerCamelCase						:					Any					,       __lowerCamelCase						:					Tuple					,       __lowerCamelCase						:					Tuple       )    ->   Optional[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        _lowercase				(		self						:					Tuple					,       __lowerCamelCase						:					Dict					,       __lowerCamelCase						:					List[str]					,       __lowerCamelCase						:					Optional[int]       )    ->   Dict:






         """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        _lowercase				(		self						:					Dict       )    ->   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     =			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 ...configuration_utils import PretrainedConfig
from ...utils import logging


__a     =			logging.get_logger(__name__)

__a     =			{"""ctrl""": """https://huggingface.co/ctrl/resolve/main/config.json"""}






class   __lowercase				(  __snake_case  ):
      UpperCamelCase								=       '''ctrl'''
      UpperCamelCase								=       ['''past_key_values''']
      UpperCamelCase								=       {
          '''max_position_embeddings''': '''n_positions''',
          '''hidden_size''': '''n_embd''',
          '''num_attention_heads''': '''n_head''',
          '''num_hidden_layers''': '''n_layer''',
      }





      def __init__(		self						:					str					,       __lowerCamelCase						:					Optional[int]=2_4_6_5_3_4					,       __lowerCamelCase						:					Union[str, Any]=2_5_6					,       __lowerCamelCase						:					int=1_2_8_0					,       __lowerCamelCase						:					Optional[Any]=8_1_9_2					,       __lowerCamelCase						:					List[str]=4_8					,       __lowerCamelCase						:					Dict=1_6					,       __lowerCamelCase						:					Union[str, Any]=0.1					,       __lowerCamelCase						:					Union[str, Any]=0.1					,       __lowerCamelCase						:					Union[str, Any]=1e-6					,       __lowerCamelCase						:					str=0.02					,       __lowerCamelCase						:					Union[str, Any]=True					,       **__lowerCamelCase						:					List[str]					,       )    ->   Optional[Any]:






         """simple docstring"""







         UpperCAmelCase							=     vocab_size
         UpperCAmelCase							=     n_positions
         UpperCAmelCase							=     n_embd
         UpperCAmelCase							=     n_layer
         UpperCAmelCase							=     n_head
         UpperCAmelCase							=     dff
         UpperCAmelCase							=     resid_pdrop
         UpperCAmelCase							=     embd_pdrop
         UpperCAmelCase							=     layer_norm_epsilon
         UpperCAmelCase							=     initializer_range

         UpperCAmelCase							=     use_cache

         super().__init__(**__lowerCamelCase       )



