'''simple docstring'''






from collections.abc import Sequence
from queue import Queue







class lowercase_       :







   """simple docstring"""

   def __init__(      self      :			Tuple, UpperCamelCase__      :			Any, UpperCamelCase__      :			List[Any], UpperCamelCase__      :			Optional[int], UpperCamelCase__      :			Optional[int]=None, UpperCamelCase__      :			Tuple=None     )  ->			Any:
        _A    		=  start
        _A    		=  end
        _A    		=  val
        _A    		=  (start + end) // 2
        _A    		=  left
        _A    		=  right

   def __repr__(      self      :			str     )  ->			Optional[int]:
        return f'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'







class lowercase_       :







   """simple docstring"""

   def __init__(      self      :			Dict, UpperCamelCase__      :			Sequence, UpperCamelCase__      :			Any     )  ->			Optional[Any]:
        _A    		=  collection
        _A    		=  function
        if self.collection:
             _A    		=  self._build_tree(0, len(UpperCamelCase__     ) - 1     )
   def 	__UpperCAmelCase   (      self      :			Any, UpperCamelCase__      :			str, UpperCamelCase__      :			Dict     )  ->			int:
        self._update_tree(self.root, UpperCamelCase__, UpperCamelCase__     )
   def 	__UpperCAmelCase   (      self      :			Union[str, Any], UpperCamelCase__      :			List[Any], UpperCamelCase__      :			Optional[Any]     )  ->			Union[str, Any]:
        return self._query_range(self.root, UpperCamelCase__, UpperCamelCase__     )
   def 	__UpperCAmelCase   (      self      :			Optional[Any], UpperCamelCase__      :			Any, UpperCamelCase__      :			List[Any]     )  ->			str:
        if start == end:
             return SegmentTreeNode(UpperCamelCase__, UpperCamelCase__, self.collection[start]     )
        _A    		=  (start + end) // 2
        _A    		=  self._build_tree(UpperCamelCase__, UpperCamelCase__     )
        _A    		=  self._build_tree(mid + 1, UpperCamelCase__     )
        return SegmentTreeNode(UpperCamelCase__, UpperCamelCase__, self.fn(left.val, right.val     ), UpperCamelCase__, UpperCamelCase__     )
   def 	__UpperCAmelCase   (      self      :			List[Any], UpperCamelCase__      :			Any, UpperCamelCase__      :			Union[str, Any], UpperCamelCase__      :			Optional[int]     )  ->			Tuple:
        if node.start == i and node.end == i:
             _A    		=  val
             return
        if i <= node.mid:
             self._update_tree(node.left, UpperCamelCase__, UpperCamelCase__     )
        else:
             self._update_tree(node.right, UpperCamelCase__, UpperCamelCase__     )
        _A    		=  self.fn(node.left.val, node.right.val     )
   def 	__UpperCAmelCase   (      self      :			Tuple, UpperCamelCase__      :			List[str], UpperCamelCase__      :			Tuple, UpperCamelCase__      :			int     )  ->			Tuple:
        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 	__UpperCAmelCase   (      self      :			List[Any]     )  ->			List[Any]:
        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    :     Tuple         =       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  _SCREAMING_SNAKE_CASE		(      __snake_case							:			str   ,		__snake_case							:			str   ,		__snake_case							:			List[Any]=False				):

     if isinstance(__snake_case   ,		__snake_case				) and isinstance(__snake_case   ,		__snake_case				):
          _A    		=  len(set_a.intersection(__snake_case				)				)

          if alternative_union:
               _A    		=  len(__snake_case				) + len(__snake_case				)
          else:
               _A    		=  len(set_a.union(__snake_case				)				)

          return intersection / union

     if isinstance(__snake_case   ,		(list, tuple)				) and isinstance(__snake_case   ,		(list, tuple)				):
          _A    		=  [element for element in set_a if element in set_b]

          if alternative_union:
               _A    		=  len(__snake_case				) + len(__snake_case				)
               return len(__snake_case				) / union
          else:
               _A    		=  set_a + [element for element in set_b if element not in set_a]
               return len(__snake_case				) / len(__snake_case				)

          return len(__snake_case				) / len(__snake_case				)
     return None


if __name__ == "__main__":
   _UpperCAmelCase    :     Optional[Any]         =       {'''a''', '''b''', '''c''', '''d''', '''e'''}
   _UpperCAmelCase    :     str         =       {'''c''', '''d''', '''e''', '''f''', '''h''', '''i'''}
   print(jaccard_similarity(set_a, set_b))



