


"""simple docstring"""







from collections.abc import Callable
from math import pi, sqrt
from random import uniform
from statistics import mean




def      UpperCAmelCase__ (lowerCAmelCase_     ):




					'''simple docstring'''


					def is_in_circle(lowerCAmelCase_						,		lowerCAmelCase_     ) -> bool:
										__SCREAMING_SNAKE_CASE		     =       sqrt((x**2) + (y**2)     )
										# Our circle has a radius of 1, so a distance
										# greater than 1 would land outside the circle.
										return distance_from_centre <= 1

					# The proportion of guesses that landed in the circle
					__SCREAMING_SNAKE_CASE		     =       mean(
					    int(is_in_circle(uniform(-1.0						,		1.0     )						,		uniform(-1.0						,		1.0     )     )     )
					    for _ in range(lowerCAmelCase_     )     )
					# The ratio of the area for circle to square is pi/4.
					__SCREAMING_SNAKE_CASE		     =       proportion * 4
					print(f"""The estimated value of pi is {pi_estimate}"""     )
					print(f"""The numpy value of pi is {pi}"""     )
					print(f"""The total error is {abs(pi - pi_estimate     )}"""     )




def      UpperCAmelCase__ (lowerCAmelCase_						,		lowerCAmelCase_						,		lowerCAmelCase_ = 0.0						,		lowerCAmelCase_ = 1.0						,		):




					'''simple docstring'''


					return mean(
					    function_to_integrate(uniform(lowerCAmelCase_						,		lowerCAmelCase_     )     ) for _ in range(lowerCAmelCase_     )     ) * (max_value - min_value)




def      UpperCAmelCase__ (lowerCAmelCase_						,		lowerCAmelCase_ = 0.0						,		lowerCAmelCase_ = 1.0     ):




					'''simple docstring'''


					def identity_function(lowerCAmelCase_     ) -> float:
										return x

					__SCREAMING_SNAKE_CASE		     =       area_under_curve_estimator(
					    lowerCAmelCase_						,		lowerCAmelCase_						,		lowerCAmelCase_						,		lowerCAmelCase_     )
					__SCREAMING_SNAKE_CASE		     =       (max_value * max_value - min_value * min_value) / 2

					print("******************"     )
					print(f"""Estimating area under y=x where x varies from {min_value} to {max_value}"""     )
					print(f"""Estimated value is {estimated_value}"""     )
					print(f"""Expected value is {expected_value}"""     )
					print(f"""Total error is {abs(estimated_value - expected_value     )}"""     )
					print("******************"     )




def      UpperCAmelCase__ (lowerCAmelCase_     ):




					'''simple docstring'''


					def function_to_integrate(lowerCAmelCase_     ) -> float:
										return sqrt(4.0 - x * x     )

					__SCREAMING_SNAKE_CASE		     =       area_under_curve_estimator(
					    lowerCAmelCase_						,		lowerCAmelCase_						,		0.0						,		2.0     )

					print("******************"     )
					print("Estimating pi using area_under_curve_estimator"     )
					print(f"""Estimated value is {estimated_value}"""     )
					print(f"""Expected value is {pi}"""     )
					print(f"""Total error is {abs(estimated_value - pi     )}"""     )
					print("******************"     )


if __name__ == "__main__":
		import doctest

		doctest.testmod()




"""simple docstring"""







from __future__ import annotations

import math




class 				UpperCamelCase_			:

	"""simple docstring"""





	def __init__(				self    :       Union[str, Any]    ,    UpperCAmelCase__    :       int     ) ->			None:
						__SCREAMING_SNAKE_CASE		     =       size
						# approximate the overall size of segment tree with given value
						__SCREAMING_SNAKE_CASE		     =       [0 for i in range(0    ,    4 * size     )]
						# create array to store lazy update
						__SCREAMING_SNAKE_CASE		     =       [0 for i in range(0    ,    4 * size     )]
						__SCREAMING_SNAKE_CASE		     =       [0 for i in range(0    ,    4 * size     )]  # flag for lazy update




	def 						UpperCAmelCase_   (				self    :       str    ,    UpperCAmelCase__    :       int     ) ->			int:
						return idx * 2




	def 						UpperCAmelCase_   (				self    :       Any    ,    UpperCAmelCase__    :       int     ) ->			int:
						return idx * 2 + 1




	def 						UpperCAmelCase_   (				self    :       List[Any]    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       list[int]     ) ->			None:
						if left_element == right_element:
											__SCREAMING_SNAKE_CASE		     =       a[left_element - 1]
						else:
											__SCREAMING_SNAKE_CASE		     =       (left_element + right_element) // 2
											self.build(self.left(UpperCAmelCase__     )    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
											self.build(self.right(UpperCAmelCase__     )    ,    mid + 1    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
											__SCREAMING_SNAKE_CASE		     =       max(
											    self.segment_tree[self.left(UpperCAmelCase__     )]    ,    self.segment_tree[self.right(UpperCAmelCase__     )]     )




	def 						UpperCAmelCase_   (				self    :       Tuple    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int     ) ->			bool:
						if self.flag[idx] is True:
											__SCREAMING_SNAKE_CASE		     =       self.lazy[idx]
											__SCREAMING_SNAKE_CASE		     =       False
											if left_element != right_element:
																__SCREAMING_SNAKE_CASE		     =       self.lazy[idx]
																__SCREAMING_SNAKE_CASE		     =       self.lazy[idx]
																__SCREAMING_SNAKE_CASE		     =       True
																__SCREAMING_SNAKE_CASE		     =       True

						if right_element < a or left_element > b:
											return True
						if left_element >= a and right_element <= b:
											__SCREAMING_SNAKE_CASE		     =       val
											if left_element != right_element:
																__SCREAMING_SNAKE_CASE		     =       val
																__SCREAMING_SNAKE_CASE		     =       val
																__SCREAMING_SNAKE_CASE		     =       True
																__SCREAMING_SNAKE_CASE		     =       True
											return True
						__SCREAMING_SNAKE_CASE		     =       (left_element + right_element) // 2
						self.update(self.left(UpperCAmelCase__     )    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
						self.update(self.right(UpperCAmelCase__     )    ,    mid + 1    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
						__SCREAMING_SNAKE_CASE		     =       max(
						    self.segment_tree[self.left(UpperCAmelCase__     )]    ,    self.segment_tree[self.right(UpperCAmelCase__     )]     )
						return True




	def 						UpperCAmelCase_   (				self    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int     ) ->			int | float:
						if self.flag[idx] is True:
											__SCREAMING_SNAKE_CASE		     =       self.lazy[idx]
											__SCREAMING_SNAKE_CASE		     =       False
											if left_element != right_element:
																__SCREAMING_SNAKE_CASE		     =       self.lazy[idx]
																__SCREAMING_SNAKE_CASE		     =       self.lazy[idx]
																__SCREAMING_SNAKE_CASE		     =       True
																__SCREAMING_SNAKE_CASE		     =       True
						if right_element < a or left_element > b:
											return -math.inf
						if left_element >= a and right_element <= b:
											return self.segment_tree[idx]
						__SCREAMING_SNAKE_CASE		     =       (left_element + right_element) // 2
						__SCREAMING_SNAKE_CASE		     =       self.query(self.left(UpperCAmelCase__     )    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
						__SCREAMING_SNAKE_CASE		     =       self.query(self.right(UpperCAmelCase__     )    ,    mid + 1    ,    UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
						return max(UpperCAmelCase__    ,    UpperCAmelCase__     )




	def __str__(				self    :       int     ) ->			str:
						return str([self.query(1    ,    1    ,    self.size    ,    UpperCAmelCase__    ,    UpperCAmelCase__     ) for i in range(1    ,    self.size + 1     )]     )


if __name__ == "__main__":
		a__       :							Tuple        =  [1, 2, -4, 7, 3, -5, 6, 1_1, -2_0, 9, 1_4, 1_5, 5, 2, -8]
		a__       :							Dict        =  1_5
		a__       :							int        =  SegmentTree(size)
		segt.build(1, 1, size, A)
		print(segt.query(1, 1, size, 4, 6))
		print(segt.query(1, 1, size, 7, 1_1))
		print(segt.query(1, 1, size, 7, 1_2))
		segt.update(1, 1, size, 1, 3, 1_1_1)
		print(segt.query(1, 1, size, 1, 1_5))
		segt.update(1, 1, size, 7, 8, 2_3_5)
		print(segt)
