'''simple docstring'''

import logging

# standard libraries
import sys

import numpy as np
import pytest  # type: ignore

# Custom/local libraries
from matrix import matrix_operation as matop

lowerCAmelCase_			:			Tuple    	=   [[12, 10], [3, 9]]
lowerCAmelCase_			:			Tuple    	=   [[3, 4], [7, 4]]
lowerCAmelCase_			:			Tuple    	=   [[3, 0, 2], [2, 0, -2], [0, 1, 1]]
lowerCAmelCase_			:			int    	=   [[3, 0, -2], [2, 0, 2], [0, 1, 1]]
lowerCAmelCase_			:			List[str]    	=   [[3, 0, 2], [2, 0, -2], [0, 1, 1], [2, 0, -2]]
lowerCAmelCase_			:			Union[str, Any]    	=   [1]
lowerCAmelCase_			:			Tuple    	=   [2]

lowerCAmelCase_			:			List[Any]    	=   logging.getLogger()
lowerCAmelCase_			:			Any    	=   logging.DEBUG
lowerCAmelCase_			:			List[Any]    	=   logging.StreamHandler(sys.stdout)
logger.addHandler(stream_handler)


@pytest.mark.mat_ops
@pytest.mark.parametrize(
    ("mat1", "mat2")			,		[(mat_a, mat_b), (mat_c, mat_d), (mat_d, mat_e), (mat_f, mat_h)]					)
def __a			(						__lowerCamelCase      :    Optional[Any]			,		__lowerCamelCase      :    Union[str, Any]					)						->				Any:
      '''simple docstring'''


      if (np.array(_a					)).shape < (2, 2) or (np.array(_a					)).shape < (2, 2):
            with pytest.raises(_a					):
                  logger.info(f'\n\t{test_addition.__name__} returned integer'					)
                  matop.add(_a			,		_a					)
      elif (np.array(_a					)).shape == (np.array(_a					)).shape:
            logger.info(f'\n\t{test_addition.__name__} with same matrix dims'					)
            lowercase_     			=   (np.array(_a					) + np.array(_a					)).tolist()
            lowercase_     			=   matop.add(_a			,		_a					)
            assert theo == act
      else:
            with pytest.raises(_a					):
                  logger.info(f'\n\t{test_addition.__name__} with different matrix dims'					)
                  matop.add(_a			,		_a					)


@pytest.mark.mat_ops
@pytest.mark.parametrize(
    ("mat1", "mat2")			,		[(mat_a, mat_b), (mat_c, mat_d), (mat_d, mat_e), (mat_f, mat_h)]					)
def __a			(						__lowerCamelCase      :    Union[str, Any]			,		__lowerCamelCase      :    Any					)						->				Optional[Any]:
      '''simple docstring'''


      if (np.array(_a					)).shape < (2, 2) or (np.array(_a					)).shape < (2, 2):
            with pytest.raises(_a					):
                  logger.info(f'\n\t{test_subtraction.__name__} returned integer'					)
                  matop.subtract(_a			,		_a					)
      elif (np.array(_a					)).shape == (np.array(_a					)).shape:
            logger.info(f'\n\t{test_subtraction.__name__} with same matrix dims'					)
            lowercase_     			=   (np.array(_a					) - np.array(_a					)).tolist()
            lowercase_     			=   matop.subtract(_a			,		_a					)
            assert theo == act
      else:
            with pytest.raises(_a					):
                  logger.info(f'\n\t{test_subtraction.__name__} with different matrix dims'					)
                  assert matop.subtract(_a			,		_a					)


@pytest.mark.mat_ops
@pytest.mark.parametrize(
    ("mat1", "mat2")			,		[(mat_a, mat_b), (mat_c, mat_d), (mat_d, mat_e), (mat_f, mat_h)]					)
def __a			(						__lowerCamelCase      :    List[str]			,		__lowerCamelCase      :    Dict					)						->				str:
      '''simple docstring'''


      if (np.array(_a					)).shape < (2, 2) or (np.array(_a					)).shape < (2, 2):
            logger.info(f'\n\t{test_multiplication.__name__} returned integer'					)
            with pytest.raises(_a					):
                  matop.add(_a			,		_a					)
      elif (np.array(_a					)).shape == (np.array(_a					)).shape:
            logger.info(f'\n\t{test_multiplication.__name__} meets dim requirements'					)
            lowercase_     			=   (np.matmul(_a			,		_a					)).tolist()
            lowercase_     			=   matop.multiply(_a			,		_a					)
            assert theo == act
      else:
            with pytest.raises(_a					):
                  logger.info(
                      f'\n\t{test_multiplication.__name__} does not meet dim requirements'					)
                  assert matop.subtract(_a			,		_a					)


@pytest.mark.mat_ops
def __a			(						)						->				str:
      '''simple docstring'''


      lowercase_     			=   (3.5 * np.array(_a					)).tolist()
      lowercase_     			=   matop.scalar_multiply(_a			,		3.5					)
      assert theo == act


@pytest.mark.mat_ops
def __a			(						)						->				Dict:
      '''simple docstring'''


      lowercase_     			=   (np.identity(5					)).tolist()
      lowercase_     			=   matop.identity(5					)
      assert theo == act






@pytest.mark.mat_ops
@pytest.mark.parametrize("mat"			,		[mat_a, mat_b, mat_c, mat_d, mat_e, mat_f]					)
def __a			(						__lowerCamelCase      :    Union[str, Any]					)						->				int:
      '''simple docstring'''


      if (np.array(_a					)).shape < (2, 2):
            with pytest.raises(_a					):
                  logger.info(f'\n\t{test_transpose.__name__} returned integer'					)
                  matop.transpose(_a					)
      else:
            lowercase_     			=   (np.transpose(_a					)).tolist()
            lowercase_     			=   matop.transpose(_a			,		return_map=_a					)
            assert theo == act













import math





class   lowercase__     :







  def __init__(						self     ,    _lowercase    ):
       lowerCAmelCase_       :							Optional[Any]			 =		len(_lowercase    )
       lowerCAmelCase_       :							Union[str, Any]			 =		[0] * (
           4 * self.N
       )  # approximate the overall size of segment tree with array N
       self.build(1     ,    0     ,    self.N - 1    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase    ):
       return idx * 2







  def 						UpperCAmelCase__		(						self     ,    _lowercase    ):
       return idx * 2 + 1







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):  # noqa: E741
       if l == r:
            lowerCAmelCase_       :							Dict			 =		A[l]
       else:
            lowerCAmelCase_       :							List[str]			 =		(l + r) // 2
            self.build(self.left(_lowercase    )     ,    _lowercase     ,    _lowercase    )
            self.build(self.right(_lowercase    )     ,    mid + 1     ,    _lowercase    )
            lowerCAmelCase_       :							Dict			 =		max(self.st[self.left(_lowercase    )]     ,    self.st[self.right(_lowercase    )]    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):
       return self.update_recursive(1     ,    0     ,    self.N - 1     ,    a - 1     ,    b - 1     ,    _lowercase    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):  # noqa: E741
       if r < a or l > b:
            return True
       if l == r:
            lowerCAmelCase_       :							List[str]			 =		val
            return True
       lowerCAmelCase_       :							List[str]			 =		(l + r) // 2
       self.update_recursive(self.left(_lowercase    )     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase    )
       self.update_recursive(self.right(_lowercase    )     ,    mid + 1     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase    )
       lowerCAmelCase_       :							List[Any]			 =		max(self.st[self.left(_lowercase    )]     ,    self.st[self.right(_lowercase    )]    )
       return True







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase    ):
       return self.query_recursive(1     ,    0     ,    self.N - 1     ,    a - 1     ,    b - 1    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):  # noqa: E741
       if r < a or l > b:
            return -math.inf
       if l >= a and r <= b:
            return self.st[idx]
       lowerCAmelCase_       :							int			 =		(l + r) // 2
       lowerCAmelCase_       :							List[Any]			 =		self.query_recursive(self.left(_lowercase    )     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase    )
       lowerCAmelCase_       :							List[str]			 =		self.query_recursive(self.right(_lowercase    )     ,    mid + 1     ,    _lowercase     ,    _lowercase     ,    _lowercase    )
       return max(_lowercase     ,    _lowercase    )







  def 						UpperCAmelCase__		(						self    ):
       lowerCAmelCase_       :							List[Any]			 =		[]
       for i in range(1     ,    N + 1    ):
            show_list += [self.query(_lowercase     ,    _lowercase    )]
       print(_lowercase    )


if __name__ == "__main__":
      UpperCAmelCase_       : Any							=    [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
      UpperCAmelCase_       : Optional[Any]							=    15
      UpperCAmelCase_       : 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()
