
"""simple docstring"""
from __future__ import annotations

from collections.abc import Callable
from typing import Any, Generic, TypeVar

lowercase_       :						str     					=	TypeVar('''T''')
class 			UpperCamelCase      (							Generic[T]  ):
     def __init__(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Any | T							    = None

       _SCREAMING_SNAKE_CASE   :				int							    = len(snake_case__				)
       _SCREAMING_SNAKE_CASE   :				list[T]							    = [any_type for _ in range(self.N				)] + arr
       _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = fnc
       self.build()
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       for p in range(self.N - 1  ,     0  ,     -1				):
         _SCREAMING_SNAKE_CASE   :				int							    = self.fn(self.st[p * 2]  ,     self.st[p * 2 + 1]				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       p += self.N
       _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = v
       while p > 1:
         _SCREAMING_SNAKE_CASE   :				Dict							    = p // 2
         _SCREAMING_SNAKE_CASE   :				str							    = self.fn(self.st[p * 2]  ,     self.st[p * 2 + 1]				)




     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):  # noqa: E741




       """simple docstring"""


       _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				Tuple							    = l + self.N, r + self.N

       _SCREAMING_SNAKE_CASE   :				T | None							    = None
       while l <= r:
         if l % 2 == 1:
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = self.st[l] if res is None else self.fn(snake_case__  ,     self.st[l]				)
         if r % 2 == 0:
           _SCREAMING_SNAKE_CASE   :				int							    = self.st[r] if res is None else self.fn(snake_case__  ,     self.st[r]				)
         _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = (l + 1) // 2, (r - 1) // 2
       return res


if __name__ == "__main__":
      from functools import reduce

      lowercase_       :						Union[str, Any]     					=	[1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]

      lowercase_       :						List[str]     					=	{
          0: 7,
          1: 2,
          2: 6,
          3: -14,
          4: 5,
          5: 4,
          6: 7,
          7: -10,
          8: 9,
          9: 10,
          10: 12,
          11: 1,
      }

      lowercase_       :						Any     					=	SegmentTree(test_array, min)
      lowercase_       :						Optional[Any]     					=	SegmentTree(test_array, max)
      lowercase_       :						Union[str, Any]     					=	SegmentTree(test_array, lambda a, b: a + b)





      def    _lowerCAmelCase    (     )  ->    None:
        for i in range(len(lowerCamelCase__				)				):
          for j in range(lowerCamelCase__,						len(lowerCamelCase__				)				):
            _SCREAMING_SNAKE_CASE   :				Dict							    = reduce(lowerCamelCase__,						test_array[i : j + 1]				)
            _SCREAMING_SNAKE_CASE   :				Tuple							    = reduce(lowerCamelCase__,						test_array[i : j + 1]				)
            _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = reduce(lambda lowerCamelCase__,						lowerCamelCase__				: a + b,						test_array[i : j + 1]				)
            assert min_range == min_segment_tree.query(lowerCamelCase__,						lowerCamelCase__				)
            assert max_range == max_segment_tree.query(lowerCamelCase__,						lowerCamelCase__				)
            assert sum_range == sum_segment_tree.query(lowerCamelCase__,						lowerCamelCase__				)

      test_all_segments()

      for index, value in test_updates.items():
            lowercase_       :						Optional[Any]     					=	value
            min_segment_tree.update(index, value)
            max_segment_tree.update(index, value)
            sum_segment_tree.update(index, value)
            test_all_segments()





"""simple docstring"""
from __future__ import annotations

import time
from collections.abc import Sequence
from random import randint

from matplotlib import pyplot as plt





def    _lowerCAmelCase    (     lowerCamelCase__							:							Sequence[float],						lowerCamelCase__							:							int,						lowerCamelCase__							:							int				)  ->    tuple[int | None, int | None, float]:
  if not arr:
    return None, None, 0
  if low == high:
    return low, high, arr[low]

  _SCREAMING_SNAKE_CASE   :				Any							    = (low + high) // 2
  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				Optional[int]							    = max_subarray(lowerCamelCase__,						lowerCamelCase__,						lowerCamelCase__				)
  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				List[str]							    = max_subarray(lowerCamelCase__,						mid + 1,						lowerCamelCase__				)
  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				str							    = max_cross_sum(lowerCamelCase__,						lowerCamelCase__,						lowerCamelCase__,						lowerCamelCase__				)
  if left_sum >= right_sum and left_sum >= cross_sum:
    return left_low, left_high, left_sum
  elif right_sum >= left_sum and right_sum >= cross_sum:
    return right_low, right_high, right_sum
  return cross_left, cross_right, cross_sum





def    _lowerCAmelCase    (     lowerCamelCase__							:							Sequence[float],						lowerCamelCase__							:							int,						lowerCamelCase__							:							int,						lowerCamelCase__							:							int				)  ->    tuple[int, int, float]:
  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				List[Any]							    = float("-inf"				), -1
  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				Dict							    = float("-inf"				), -1

  _SCREAMING_SNAKE_CASE   :				int | float							    = 0
  for i in range(lowerCamelCase__,						low - 1,						-1				):
    summ += arr[i]
    if summ > left_sum:
      _SCREAMING_SNAKE_CASE   :				int							    = summ
      _SCREAMING_SNAKE_CASE   :				Tuple							    = i

  _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = 0
  for i in range(mid + 1,						high + 1				):
    summ += arr[i]
    if summ > right_sum:
      _SCREAMING_SNAKE_CASE   :				int							    = summ
      _SCREAMING_SNAKE_CASE   :				Any							    = i

  return max_left, max_right, (left_sum + right_sum)





def    _lowerCAmelCase    (     lowerCamelCase__							:							int				)  ->    float:
  _SCREAMING_SNAKE_CASE   :				Any							    = [randint(1,						lowerCamelCase__				) for _ in range(lowerCamelCase__				)]
  _SCREAMING_SNAKE_CASE   :				int							    = time.time()
  max_subarray(lowerCamelCase__,						0,						input_size - 1				)
  _SCREAMING_SNAKE_CASE   :				List[str]							    = time.time()
  return end - start





def    _lowerCAmelCase    (     )  ->    None:
  _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = [1_0, 1_0_0, 1_0_0_0, 1_0_0_0_0, 5_0_0_0_0, 1_0_0_0_0_0, 2_0_0_0_0_0, 3_0_0_0_0_0, 4_0_0_0_0_0, 5_0_0_0_0_0]
  _SCREAMING_SNAKE_CASE   :				int							    = [time_max_subarray(lowerCamelCase__				) for input_size in input_sizes]
  print("No of Inputs\t\tTime Taken"				)
  for input_size, runtime in zip(lowerCamelCase__,						lowerCamelCase__				):
    print(lowerCamelCase__,						"\t\t",						lowerCamelCase__				)
  plt.plot(lowerCamelCase__,						lowerCamelCase__				)
  plt.xlabel("Number of Inputs"				)
  plt.ylabel("Time taken in seconds"				)
  plt.show()


if __name__ == "__main__":
      from doctest import testmod

      testmod()



