


'''simple docstring'''






from collections.abc import Sequence
from queue import Queue






class   __snake_case			:







    """simple docstring"""



    def __init__(  self       :    Union[str, Any]       ,		lowerCamelCase       :    Any       ,		lowerCamelCase       :    List[Any]       ,		lowerCamelCase       :    str       ,		lowerCamelCase       :    List[str]=None       ,		lowerCamelCase       :    str=None						)  ->    List[Any]:
      lowerCAmelCase_     : List[Any]     =  start
      lowerCAmelCase_     : Any     =  end
      lowerCAmelCase_     : Any     =  val
      lowerCAmelCase_     : Optional[Any]     =  (start + end) // 2
      lowerCAmelCase_     : Tuple     =  left
      lowerCAmelCase_     : Union[str, Any]     =  right





    def __repr__(  self       :    str						)  ->    List[Any]:
      return F'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'







class   __snake_case			:







    """simple docstring"""



    def __init__(  self       :    Any       ,		lowerCamelCase       :    Sequence       ,		lowerCamelCase       :    Dict						)  ->    Dict:
      lowerCAmelCase_     : Optional[Any]     =  collection
      lowerCAmelCase_     : Tuple     =  function
      if self.collection:
        lowerCAmelCase_     : Optional[int]     =  self._build_tree(0       ,		len(lowerCamelCase						) - 1						)

    def __lowercase  (  self       :    List[Any]       ,		lowerCamelCase       :    List[Any]       ,		lowerCamelCase       :    Union[str, Any]						)  ->    Any:
      self._update_tree(self.root       ,		lowerCamelCase       ,		lowerCamelCase						)

    def __lowercase  (  self       :    Dict       ,		lowerCamelCase       :    List[str]       ,		lowerCamelCase       :    Union[str, Any]						)  ->    Tuple:
      return self._query_range(self.root       ,		lowerCamelCase       ,		lowerCamelCase						)

    def __lowercase  (  self       :    Optional[int]       ,		lowerCamelCase       :    int       ,		lowerCamelCase       :    str						)  ->    str:
      if start == end:
        return SegmentTreeNode(lowerCamelCase       ,		lowerCamelCase       ,		self.collection[start]						)
      lowerCAmelCase_     : Tuple     =  (start + end) // 2
      lowerCAmelCase_     : List[Any]     =  self._build_tree(lowerCamelCase       ,		lowerCamelCase						)
      lowerCAmelCase_     : List[Any]     =  self._build_tree(mid + 1       ,		lowerCamelCase						)
      return SegmentTreeNode(lowerCamelCase       ,		lowerCamelCase       ,		self.fn(left.val       ,		right.val						)       ,		lowerCamelCase       ,		lowerCamelCase						)

    def __lowercase  (  self       :    Optional[Any]       ,		lowerCamelCase       :    List[Any]       ,		lowerCamelCase       :    Any       ,		lowerCamelCase       :    str						)  ->    str:
      if node.start == i and node.end == i:
        lowerCAmelCase_     : Any     =  val
        return
      if i <= node.mid:
        self._update_tree(node.left       ,		lowerCamelCase       ,		lowerCamelCase						)
      else:
        self._update_tree(node.right       ,		lowerCamelCase       ,		lowerCamelCase						)
      lowerCAmelCase_     : str     =  self.fn(node.left.val       ,		node.right.val						)

    def __lowercase  (  self       :    Optional[int]       ,		lowerCamelCase       :    Union[str, Any]       ,		lowerCamelCase       :    List[str]       ,		lowerCamelCase       :    Union[str, Any]						)  ->    Union[str, Any]:
      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       :    Any						)  ->    List[str]:
      if self.root is not None:
        lowerCAmelCase_     : Any     =  Queue()
        queue.put(self.root						)
        while not queue.empty():
          lowerCAmelCase_     : Union[str, Any]     =  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   :    List[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()







'''simple docstring'''






def 							UpperCamelCase_     (       A__   :  bytes   ):
  '''simple docstring'''





  return "".join([hex(A__   )[2:].zfill(2   ).upper() for byte in list(A__   )]   )







def 							UpperCamelCase_     (       A__   :  str   ):
  '''simple docstring'''





  if (len(A__   ) % 2) != 0:
    raise ValueError(
        """Base16 encoded data is invalid:
Data does not have an even number of hex digits."""   )
  # Check the character set - the standard base16 alphabet
  # is uppercase according to RFC3548 section 6
  if not set(A__   ) <= set("""0123456789ABCDEF"""   ):
    raise ValueError(
        """Base16 encoded data is invalid:
Data is not uppercase hex or it contains invalid characters."""   )
  # For every two hexadecimal digits (= a byte), turn it into an integer.
  # Then, string the result together into bytes, and return it.
  return bytes(int(data[i] + data[i + 1]				,       16   ) for i in range(0				,       len(A__   )				,       2   )   )


if __name__ == "__main__":
  import doctest

  doctest.testmod()



