



from __future__ import annotations

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

_lowerCamelCase						    =  TypeVar("""T""")

class       _SCREAMING_SNAKE_CASE	(Generic[T] ):





     def __init__(       self :							Tuple     ,  UpperCamelCase :							list[T]     ,  UpperCamelCase :							Callable[[T, T], T]				)->str:
      __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	None

      __SCREAMING_SNAKE_CASE       :    Optional[int]       =	len(__SCREAMING_SNAKE_CASE				)
      __SCREAMING_SNAKE_CASE       :    Dict       =	[any_type for _ in range(self.N				)] + arr
      __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	fnc
      self.build()





     def 	__snake_case    (       self :							Optional[int]				)->Tuple:

      for p in range(self.N - 1     ,  0     ,  -1				):
       __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	self.fn(self.st[p * 2]     ,  self.st[p * 2 + 1]				)





     def 	__snake_case    (       self :							List[Any]     ,  UpperCamelCase :							int     ,  UpperCamelCase :							T				)->List[str]:
      p += self.N
      __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	v
      while p > 1:
       __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	p // 2
       __SCREAMING_SNAKE_CASE       :    List[Any]       =	self.fn(self.st[p * 2]     ,  self.st[p * 2 + 1]				)






     def 	__snake_case    (       self :							List[Any]     ,  UpperCamelCase :							int     ,  UpperCamelCase :							int				)->Union[str, Any]:  # noqa: E741
      __SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       :    Tuple       =	l + self.N, r + self.N

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


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

      _lowerCamelCase						    =  [1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]

      _lowerCamelCase						    =  {
          0: 7,
          1: 2,
          2: 6,
          3: -14,
          4: 5,
          5: 4,
          6: 7,
          7: -10,
          8: 9,
          9: 10,
          10: 12,
          11: 1,
      }

      _lowerCamelCase						    =  SegmentTree(test_array, min)
      _lowerCamelCase						    =  SegmentTree(test_array, max)
      _lowerCamelCase						    =  SegmentTree(test_array, lambda a, b: a + b)






      def 	_lowerCAmelCase						(				):



       """simple docstring"""





       for i in range(len(_UpperCAmelCase     )     ):
        for j in range(_UpperCAmelCase		,	len(_UpperCAmelCase     )     ):
         __SCREAMING_SNAKE_CASE       :    int       =	reduce(_UpperCAmelCase		,	test_array[i : j + 1]     )
         __SCREAMING_SNAKE_CASE       :    Optional[int]       =	reduce(_UpperCAmelCase		,	test_array[i : j + 1]     )
         __SCREAMING_SNAKE_CASE       :    List[Any]       =	reduce(lambda __lowerCamelCase		,	__lowerCamelCase     : a + b		,	test_array[i : j + 1]     )
         assert min_range == min_segment_tree.query(_UpperCAmelCase		,	_UpperCAmelCase     )
         assert max_range == max_segment_tree.query(_UpperCAmelCase		,	_UpperCAmelCase     )
         assert sum_range == sum_segment_tree.query(_UpperCAmelCase		,	_UpperCAmelCase     )

      test_all_segments()

      for index, value in test_updates.items():
            _lowerCamelCase						    =  value
            min_segment_tree.update(index, value)
            max_segment_tree.update(index, value)
            sum_segment_tree.update(index, value)
            test_all_segments()





from .constants import (
    MODEL_NAME,
    OPTIMIZER_NAME,
    RNG_STATE_NAME,
    SAFE_WEIGHTS_INDEX_NAME,
    SAFE_WEIGHTS_NAME,
    SCALER_NAME,
    SCHEDULER_NAME,
    TORCH_LAUNCH_PARAMS,
    WEIGHTS_INDEX_NAME,
    WEIGHTS_NAME,
)
from .dataclasses import (
    BnbQuantizationConfig,
    ComputeEnvironment,
    CustomDtype,
    DeepSpeedPlugin,
    DistributedDataParallelKwargs,
    DistributedType,
    DynamoBackend,
    FPaRecipeKwargs,
    FullyShardedDataParallelPlugin,
    GradientAccumulationPlugin,
    GradScalerKwargs,
    InitProcessGroupKwargs,
    KwargsHandler,
    LoggerType,
    MegatronLMPlugin,
    PrecisionType,
    ProjectConfiguration,
    RNGType,
    SageMakerDistributedType,
    TensorInformation,
    TorchDynamoPlugin,
)
from .environment import get_int_from_env, parse_choice_from_env, parse_flag_from_env
from .imports import (
    get_ccl_version,
    is_abit_bnb_available,
    is_abit_bnb_available,
    is_aim_available,
    is_bfaa_available,
    is_bnb_available,
    is_botoa_available,
    is_ccl_available,
    is_comet_ml_available,
    is_datasets_available,
    is_deepspeed_available,
    is_fpa_available,
    is_ipex_available,
    is_megatron_lm_available,
    is_mlflow_available,
    is_mps_available,
    is_npu_available,
    is_rich_available,
    is_safetensors_available,
    is_sagemaker_available,
    is_tensorboard_available,
    is_tpu_available,
    is_transformers_available,
    is_wandb_available,
    is_xpu_available,
)
from .modeling import (
    check_device_map,
    check_tied_parameters_in_config,
    check_tied_parameters_on_same_device,
    compute_module_sizes,
    convert_file_size_to_int,
    dtype_byte_size,
    find_tied_parameters,
    get_balanced_memory,
    get_max_layer_size,
    get_max_memory,
    get_mixed_precision_context_manager,
    id_tensor_storage,
    infer_auto_device_map,
    load_checkpoint_in_model,
    load_offloaded_weights,
    load_state_dict,
    named_module_tensors,
    retie_parameters,
    set_module_tensor_to_device,
    shard_checkpoint,
)
from .offload import (
    OffloadedWeightsLoader,
    PrefixedDataset,
    extract_submodules_state_dict,
    load_offloaded_weight,
    offload_state_dict,
    offload_weight,
    save_offload_index,
)
from .operations import (
    broadcast,
    broadcast_object_list,
    concatenate,
    convert_outputs_to_fpaa,
    convert_to_fpaa,
    find_batch_size,
    find_device,
    gather,
    gather_object,
    get_data_structure,
    honor_type,
    initialize_tensors,
    is_namedtuple,
    is_tensor_information,
    is_torch_tensor,
    listify,
    pad_across_processes,
    recursively_apply,
    reduce,
    send_to_device,
    slice_tensors,
)
from .versions import compare_versions, is_torch_version


if is_deepspeed_available():
      from .deepspeed import (
          DeepSpeedEngineWrapper,
          DeepSpeedOptimizerWrapper,
          DeepSpeedSchedulerWrapper,
          DummyOptim,
          DummyScheduler,
          HfDeepSpeedConfig,
      )

from .bnb import has_abit_bnb_layers, load_and_quantize_model
from .fsdp_utils import load_fsdp_model, load_fsdp_optimizer, save_fsdp_model, save_fsdp_optimizer
from .launch import (
    PrepareForLaunch,
    _filter_args,
    prepare_deepspeed_cmd_env,
    prepare_multi_gpu_env,
    prepare_sagemager_args_inputs,
    prepare_simple_launcher_cmd_env,
    prepare_tpu,
)
from .megatron_lm import (
    AbstractTrainStep,
    BertTrainStep,
    GPTTrainStep,
    MegatronEngine,
    MegatronLMDummyDataLoader,
    MegatronLMDummyScheduler,
    MegatronLMOptimizerWrapper,
    MegatronLMSchedulerWrapper,
    TaTrainStep,
    avg_losses_across_data_parallel_group,
    gather_across_data_parallel_groups,
)
from .megatron_lm import initialize as megatron_lm_initialize
from .megatron_lm import prepare_data_loader as megatron_lm_prepare_data_loader
from .megatron_lm import prepare_model as megatron_lm_prepare_model
from .megatron_lm import prepare_optimizer as megatron_lm_prepare_optimizer
from .megatron_lm import prepare_scheduler as megatron_lm_prepare_scheduler
from .memory import find_executable_batch_size, release_memory
from .other import (
    extract_model_from_parallel,
    get_pretty_name,
    is_port_in_use,
    merge_dicts,
    patch_environment,
    save,
    wait_for_everyone,
    write_basic_config,
)
from .random import set_seed, synchronize_rng_state, synchronize_rng_states
from .torch_xla import install_xla
from .tqdm import tqdm
from .transformer_engine import convert_model, has_transformer_engine_layers






