

"""simple docstring"""






def 	lowercase      (   __UpperCamelCase						) ->      Tuple:
 __magic_name__     =      generate_pascal_triangle(__UpperCamelCase						)
 for row_idx in range(__UpperCamelCase						):
  # Print left spaces
  for _ in range(num_rows - row_idx - 1						):
   print(end=''' '''						)
  # Print row values
  for col_idx in range(row_idx + 1						):
   if col_idx != row_idx:
    print(triangle[row_idx][col_idx]      ,   end=''' '''						)
   else:
    print(triangle[row_idx][col_idx]      ,   end=''''''						)
  print()





def 	lowercase      (   __UpperCamelCase						) ->      Dict:

 if not isinstance(__UpperCamelCase      ,   __UpperCamelCase						):
  raise TypeError('''The input value of \'num_rows\' should be \'int\''''						)

 if num_rows == 0:
  return []
 elif num_rows < 0:
  raise ValueError(
      '''The input value of \'num_rows\' should be greater than or equal to 0'''						)

 __magic_name__     =      []
 for current_row_idx in range(__UpperCamelCase						):
  __magic_name__     =      populate_current_row(__UpperCamelCase      ,   __UpperCamelCase						)
  triangle.append(__UpperCamelCase						)
 return triangle





def 	lowercase      (   __UpperCamelCase      ,   __UpperCamelCase						) ->      Optional[Any]:
 __magic_name__     =      [-1] * (current_row_idx + 1)
 # first and last elements of current row are equal to 1
 __magic_name__     =      1, 1
 for current_col_idx in range(1      ,   __UpperCamelCase						):
  calculate_current_element(
      __UpperCamelCase      ,   __UpperCamelCase      ,   __UpperCamelCase      ,   __UpperCamelCase						)
 return current_row





def 	lowercase      (   __UpperCamelCase      ,   __UpperCamelCase      ,   __UpperCamelCase      ,   __UpperCamelCase      ,   ) ->      str:
 __magic_name__     =      triangle[current_row_idx - 1][current_col_idx - 1]
 __magic_name__     =      triangle[current_row_idx - 1][current_col_idx]
 __magic_name__     =      above_to_left_elt + above_to_right_elt





def 	lowercase      (   __UpperCamelCase						) ->      Union[str, Any]:

 if not isinstance(__UpperCamelCase      ,   __UpperCamelCase						):
  raise TypeError('''The input value of \'num_rows\' should be \'int\''''						)

 if num_rows == 0:
  return []
 elif num_rows < 0:
  raise ValueError(
      '''The input value of \'num_rows\' should be greater than or equal to 0'''						)

 __magic_name__     =      [[1]]

 for row_index in range(1      ,   __UpperCamelCase						):
  __magic_name__     =      [0] + result[-1] + [0]
  __magic_name__     =      row_index + 1
  # Calculate the number of distinct elements in a row
  __magic_name__     =      sum(divmod(__UpperCamelCase      ,   2						)						)
  __magic_name__     =      [
      temp_row[i - 1] + temp_row[i] for i in range(1      ,   distinct_elements + 1						)
  ]
  __magic_name__     =      row_first_half[: (row_index + 1) // 2]
  row_second_half.reverse()
  __magic_name__     =      row_first_half + row_second_half
  result.append(__UpperCamelCase						)

 return result





def 	lowercase      (   ) ->      Dict:
 from collections.abc import Callable
 from timeit import timeit

 def benchmark_a_function(__UpperCamelCase      ,   __UpperCamelCase						) -> None:
  __magic_name__     =      f'''{func.__name__}({value})'''
  __magic_name__     =      timeit(f'''__main__.{call}'''      ,   setup='''import __main__'''						)
  # print(f"{call:38} = {func(value)} -- {timing:.4f} seconds")
  print(f'''{call:38} -- {timing:.4f} seconds'''						)

 for value in range(15						):  # (1, 7, 14):
  for func in (generate_pascal_triangle, generate_pascal_triangle_optimized):
   benchmark_a_function(__UpperCamelCase      ,   __UpperCamelCase						)
  print()


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  benchmark()




"""simple docstring"""






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







     def __init__(      self ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_=None ,						UpperCamelCase_=None       ):
      __magic_name__     =      start
      __magic_name__     =      end
      __magic_name__     =      val
      __magic_name__     =      (start + end) // 2
      __magic_name__     =      left
      __magic_name__     =      right







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


class        _lowercase					:







     def __init__(      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      __magic_name__     =      collection
      __magic_name__     =      function
      if self.collection:
       __magic_name__     =      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]       )
      __magic_name__     =      (start + end) // 2
      __magic_name__     =      self._build_tree(UpperCamelCase_ ,						UpperCamelCase_       )
      __magic_name__     =      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:
       __magic_name__     =      val
       return
      if i <= node.mid:
       self._update_tree(node.left ,						UpperCamelCase_ ,						UpperCamelCase_       )
      else:
       self._update_tree(node.right ,						UpperCamelCase_ ,						UpperCamelCase_       )
      __magic_name__     =      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:
       __magic_name__     =      Queue()
       queue.put(self.root       )
       while not queue.empty():
        __magic_name__     =      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)
  __lowerCamelCase										=		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()

