from typing import Any

import numpy as np
def 					UpperCamelCase__		(							A__       )  ->   bool:
				assert np.shape(A__       )[0] == np.shape(A__       )[1]

				# If matrix not symmetric, exit right away.
				if np.allclose(A__     ,					matrix.T       ) is False:
								return False

				# Get eigenvalues and eignevectors for a symmetric matrix.
				snake_case__				,    snake_case__   :      Tuple   				= np.linalg.eigh(A__       )

				# Check sign of all eigenvalues.
				# np.all returns a value of type np.bool_
				return bool(np.all(eigen_values > 0       )       )
def 					UpperCamelCase__		(							A__       )  ->   Any:
				snake_case__   :      Dict   				= np.random.randn(A__     ,					A__       )
				snake_case__   :      Optional[int]   				= np.dot(A__     ,					random_matrix.T       )
				assert _is_matrix_spd(A__       )
				return spd_matrix
def 					UpperCamelCase__		(							A__     ,					A__     ,					A__ = 1000     ,					A__ = 1e-8     ,					)  ->   Any:
				assert np.shape(A__       )[0] == np.shape(A__       )[1]
				assert np.shape(A__       )[0] == np.shape(A__       )[0]
				assert _is_matrix_spd(A__       )

				# Initialize solution guess, residual, search direction.
				snake_case__   :      int   				= np.zeros((np.shape(A__       )[0], 1)       )
				snake_case__   :      List[Any]   				= np.copy(A__       )
				snake_case__   :      Optional[int]   				= np.copy(A__       )

				# Set initial errors in solution guess and residual.
				snake_case__   :      Any   				= 1e9
				snake_case__   :      List[Any]   				= 1e9
				snake_case__   :      Dict   				= 1e9

				# Set iteration counter to threshold number of iterations.
				snake_case__   :      str   				= 0

				while error > tol:
								# Save this value so we only calculate the matrix-vector product once.
								snake_case__   :      Optional[Any]   				= np.dot(A__     ,					A__       )

								# The main algorithm.

								# Update search direction magnitude.
								snake_case__   :      Optional[Any]   				= np.dot(ra.T     ,					A__       ) / np.dot(pa.T     ,					A__       )
								# Update solution guess.
								snake_case__   :      Any   				= xa + alpha * pa
								# Calculate new residual.
								snake_case__   :      int   				= ra - alpha * w
								# Calculate new Krylov subspace scale.
								snake_case__   :      int   				= np.dot(r.T     ,					A__       ) / np.dot(ra.T     ,					A__       )
								# Calculate new A conjuage search direction.
								snake_case__   :      int   				= r + beta * pa

								# Calculate errors.
								snake_case__   :      Union[str, Any]   				= np.linalg.norm(r - ra       )
								snake_case__   :      Tuple   				= np.linalg.norm(x - xa       )
								snake_case__   :      Optional[int]   				= np.maximum(A__     ,					A__       )

								# Update variables.
								snake_case__   :      Any   				= np.copy(A__       )
								snake_case__   :      int   				= np.copy(A__       )
								snake_case__   :      Tuple   				= np.copy(A__       )

								# Update number of iterations.
								iterations += 1
								if iterations > max_iterations:
												break

				return x
def 					UpperCamelCase__		(							)  ->   None:
				snake_case__   :      List[str]   				= 3
				snake_case__   :      List[str]   				= _create_spd_matrix(A__       )
				snake_case__   :      Any   				= np.random.randn(A__     ,					1       )
				snake_case__   :      Any   				= np.dot(A__     ,					A__       )

				# Numpy solution.
				snake_case__   :      List[Any]   				= np.linalg.solve(A__     ,					A__       )

				# Our implementation.
				snake_case__   :      int   				= conjugate_gradient(A__     ,					A__       )

				# Ensure both solutions are close to x_true (and therefore one another).
				assert np.linalg.norm(x_numpy - x_true       ) <= 1e-6
				assert np.linalg.norm(x_conjugate_gradient - x_true       ) <= 1e-6


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				test_conjugate_gradient()



import math





class 					__snake_case    :




					def __init__(  self       ,			__UpperCamelCase						)	->    Dict:



									'''simple docstring'''







									snake_case__   :      Optional[int]   				= len(__UpperCamelCase						)
									snake_case__   :      Dict   				= [0] * (
									    4 * self.N
									)  # approximate the overall size of segment tree with array N
									self.build(1       ,			0       ,			self.N - 1						)




					def      __a     (  self       ,			__UpperCamelCase						)	->    Any:



									'''simple docstring'''







									return idx * 2




					def      __a     (  self       ,			__UpperCamelCase						)	->    Optional[int]:



									'''simple docstring'''







									return idx * 2 + 1




					def      __a     (  self       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)	->    int:  # noqa: E741



									'''simple docstring'''







									if l == r:
													snake_case__   :      Dict   				= A[l]
									else:
													snake_case__   :      Optional[Any]   				= (l + r) // 2
													self.build(self.left(__UpperCamelCase						)       ,			__UpperCamelCase       ,			__UpperCamelCase						)
													self.build(self.right(__UpperCamelCase						)       ,			mid + 1       ,			__UpperCamelCase						)
													snake_case__   :      int   				= max(self.st[self.left(__UpperCamelCase						)]       ,			self.st[self.right(__UpperCamelCase						)]						)




					def      __a     (  self       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)	->    int:



									'''simple docstring'''







									return self.update_recursive(1       ,			0       ,			self.N - 1       ,			a - 1       ,			b - 1       ,			__UpperCamelCase						)




					def      __a     (  self       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)	->    Tuple:  # noqa: E741



									'''simple docstring'''







									if r < a or l > b:
													return True
									if l == r:
													snake_case__   :      List[str]   				= val
													return True
									snake_case__   :      str   				= (l + r) // 2
									self.update_recursive(self.left(__UpperCamelCase						)       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)
									self.update_recursive(self.right(__UpperCamelCase						)       ,			mid + 1       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)
									snake_case__   :      Tuple   				= max(self.st[self.left(__UpperCamelCase						)]       ,			self.st[self.right(__UpperCamelCase						)]						)
									return True




					def      __a     (  self       ,			__UpperCamelCase       ,			__UpperCamelCase						)	->    List[str]:



									'''simple docstring'''







									return self.query_recursive(1       ,			0       ,			self.N - 1       ,			a - 1       ,			b - 1						)




					def      __a     (  self       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)	->    Optional[int]:  # noqa: E741



									'''simple docstring'''







									if r < a or l > b:
													return -math.inf
									if l >= a and r <= b:
													return self.st[idx]
									snake_case__   :      str   				= (l + r) // 2
									snake_case__   :      Optional[Any]   				= self.query_recursive(self.left(__UpperCamelCase						)       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)
									snake_case__   :      List[str]   				= self.query_recursive(self.right(__UpperCamelCase						)       ,			mid + 1       ,			__UpperCamelCase       ,			__UpperCamelCase       ,			__UpperCamelCase						)
									return max(__UpperCamelCase       ,			__UpperCamelCase						)




					def      __a     (  self						)	->    Optional[Any]:



									'''simple docstring'''







									snake_case__   :      Tuple   				= []
									for i in range(1       ,			N + 1						):
													show_list += [self.query(__UpperCamelCase       ,			__UpperCamelCase						)]
									print(__UpperCamelCase						)


if __name__ == "__main__":
				lowerCAmelCase__	:  Optional[int]						=  [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
				lowerCAmelCase__	:  Any						=  15
				lowerCAmelCase__	:  List[Any]						=  SegmentTree(A)
				print(segt.query(4, 6))
				print(segt.query(7, 11))
				print(segt.query(7, 12))
				segt.update(1, 3, 1_11)
				print(segt.query(1, 15))
				segt.update(7, 8, 2_35)
				segt.show_data()


