
"""simple docstring"""




import copy
import inspect

from transformers.testing_utils import require_torch, torch_device
from transformers.utils.backbone_utils import BackboneType







@require_torch
class 						lowercase:
     __snake_case:  Tuple  				=    ()
     __snake_case:  Union[str, Any]  				=    True



     def  lowercase__     (       self      )		->    Union[str, Any]:







         """simple docstring"""



         a__    = self.config_class

         # test default config
         a__    = config_class()
         self.assertIsNotNone(__SCREAMING_SNAKE_CASE      )
         a__    = ['stem'] + [f'stage{idx}' for idx in range(1    ,							len(config.depths      ) + 1      )]
         self.assertEqual(config.stage_names    ,							__SCREAMING_SNAKE_CASE      )
         self.assertTrue(set(config.out_features      ).issubset(set(config.stage_names      )      )      )

         # Test out_features and out_indices are correctly set
         # out_features and out_indices both None
         a__    = config_class(out_features=__SCREAMING_SNAKE_CASE    ,							out_indices=__SCREAMING_SNAKE_CASE      )
         self.assertEqual(config.out_features    ,							[config.stage_names[-1]]      )
         self.assertEqual(config.out_indices    ,							[len(config.stage_names      ) - 1]      )

         # out_features and out_indices both set
         a__    = config_class(out_features=['stem', 'stage1']    ,							out_indices=[0, 1]      )
         self.assertEqual(config.out_features    ,							['stem', 'stage1']      )
         self.assertEqual(config.out_indices    ,							[0, 1]      )

         # Only out_features set
         a__    = config_class(out_features=['stage1', 'stage3']      )
         self.assertEqual(config.out_features    ,							['stage1', 'stage3']      )
         self.assertEqual(config.out_indices    ,							[1, 3]      )

         # Only out_indices set
         a__    = config_class(out_indices=[0, 2]      )
         self.assertEqual(config.out_features    ,							[config.stage_names[0], config.stage_names[2]]      )
         self.assertEqual(config.out_indices    ,							[0, 2]      )

         # Error raised when out_indices do not correspond to out_features
         with self.assertRaises(__SCREAMING_SNAKE_CASE      ):
             a__    = config_class(out_features=['stage1', 'stage2']    ,							out_indices=[0, 2]      )



     def  lowercase__     (       self      )		->    Union[str, Any]:







         """simple docstring"""



         a__  ,    a__    = self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             a__    = inspect.signature(model.forward      )
             # signature.parameters is an OrderedDict => so arg_names order is deterministic
             a__    = [*signature.parameters.keys()]
             a__    = ['pixel_values']
             self.assertListEqual(arg_names[:1]    ,							__SCREAMING_SNAKE_CASE      )



     def  lowercase__     (       self      )		->    List[str]:







         """simple docstring"""



         a__  ,    a__    = self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             self.assertEqual(len(model.channels      )    ,							len(config.out_features      )      )
             a__    = model.num_features
             a__    = [config.stage_names.index(__SCREAMING_SNAKE_CASE      ) for feat in config.out_features]
             a__    = [num_features[idx] for idx in out_indices]
             self.assertListEqual(model.channels    ,							__SCREAMING_SNAKE_CASE      )

             a__    = copy.deepcopy(__SCREAMING_SNAKE_CASE      )
             a__    = None
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             self.assertEqual(len(model.channels      )    ,							1      )
             self.assertListEqual(model.channels    ,							[num_features[-1]]      )

             a__    = copy.deepcopy(__SCREAMING_SNAKE_CASE      )
             a__    = None
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             self.assertEqual(len(model.channels      )    ,							1      )
             self.assertListEqual(model.channels    ,							[num_features[-1]]      )



     def  lowercase__     (       self      )		->    Dict:







         """simple docstring"""



         a__  ,    a__    = self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             model.to(__SCREAMING_SNAKE_CASE      )
             model.eval()
             a__    = model(**__SCREAMING_SNAKE_CASE      )

             self.assertEqual(len(result.feature_maps      )    ,							len(config.out_features      )      )
             self.assertEqual(len(model.channels      )    ,							len(config.out_features      )      )
             self.assertEqual(len(result.feature_maps      )    ,							len(config.out_indices      )      )
             self.assertEqual(len(model.channels      )    ,							len(config.out_indices      )      )

             # Check output of last stage is taken if out_features=None, out_indices=None
             a__    = copy.deepcopy(__SCREAMING_SNAKE_CASE      )
             a__    = None
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             model.to(__SCREAMING_SNAKE_CASE      )
             model.eval()
             a__    = model(**__SCREAMING_SNAKE_CASE      )

             self.assertEqual(len(result.feature_maps      )    ,							1      )
             self.assertEqual(len(model.channels      )    ,							1      )

             a__    = copy.deepcopy(__SCREAMING_SNAKE_CASE      )
             a__    = None
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             model.to(__SCREAMING_SNAKE_CASE      )
             model.eval()
             a__    = model(**__SCREAMING_SNAKE_CASE      )

             self.assertEqual(len(result.feature_maps      )    ,							1      )
             self.assertEqual(len(model.channels      )    ,							1      )

             # Check backbone can be initialized with fresh weights
             a__    = copy.deepcopy(__SCREAMING_SNAKE_CASE      )
             a__    = False
             a__    = model_class(__SCREAMING_SNAKE_CASE      )
             model.to(__SCREAMING_SNAKE_CASE      )
             model.eval()
             a__    = model(**__SCREAMING_SNAKE_CASE      )



     def  lowercase__     (       self      )		->    Any:







         """simple docstring"""



         a__  ,    a__    = self.model_tester.prepare_config_and_inputs_for_common()

         for backbone_class in self.all_model_classes:
             a__    = backbone_class(__SCREAMING_SNAKE_CASE      )

             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'backbone_type'      )      )
             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'stage_names'      )      )
             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'num_features'      )      )
             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'out_indices'      )      )
             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'out_features'      )      )
             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'out_feature_channels'      )      )
             self.assertTrue(hasattr(__SCREAMING_SNAKE_CASE    ,							'channels'      )      )

             self.assertIsInstance(backbone.backbone_type    ,							__SCREAMING_SNAKE_CASE      )
             # Verify num_features has been initialized in the backbone init
             self.assertIsNotNone(backbone.num_features      )
             self.assertTrue(len(backbone.channels      ) == len(backbone.out_indices      )      )
             self.assertTrue(len(backbone.stage_names      ) == len(backbone.num_features      )      )
             self.assertTrue(len(backbone.channels      ) <= len(backbone.num_features      )      )
             self.assertTrue(len(backbone.out_feature_channels      ) == len(backbone.stage_names      )      )




     def  lowercase__     (       self      )		->    Tuple:







         """simple docstring"""



         a__  ,    a__    = self.model_tester.prepare_config_and_inputs_for_common()
         a__    = inputs_dict['pixel_values'].shape[0]

         for backbone_class in self.all_model_classes:
             a__    = backbone_class(__SCREAMING_SNAKE_CASE      )
             backbone.to(__SCREAMING_SNAKE_CASE      )
             backbone.eval()

             a__    = backbone(**__SCREAMING_SNAKE_CASE      )

             # Test default outputs and verify feature maps
             self.assertIsInstance(outputs.feature_maps    ,							__SCREAMING_SNAKE_CASE      )
             self.assertTrue(len(outputs.feature_maps      ) == len(backbone.channels      )      )
             for feature_map, n_channels in zip(outputs.feature_maps    ,							backbone.channels      ):
                 self.assertTrue(feature_map.shape[:2]    ,							(batch_size, n_channels)      )
             self.assertIsNone(outputs.hidden_states      )
             self.assertIsNone(outputs.attentions      )

             # Test output_hidden_states=True
             a__    = backbone(**__SCREAMING_SNAKE_CASE    ,							output_hidden_states=__SCREAMING_SNAKE_CASE      )
             self.assertIsNotNone(outputs.hidden_states      )
             self.assertTrue(len(outputs.hidden_states      )    ,							len(backbone.stage_names      )      )
             for hidden_state, n_channels in zip(outputs.hidden_states    ,							backbone.channels      ):
                 self.assertTrue(hidden_state.shape[:2]    ,							(batch_size, n_channels)      )

             # Test output_attentions=True
             if self.has_attentions:
                 a__    = backbone(**__SCREAMING_SNAKE_CASE    ,							output_attentions=__SCREAMING_SNAKE_CASE      )
                 self.assertIsNotNone(outputs.attentions      )




"""simple docstring"""




import math







class 						lowercase:



     def __init__(       self    ,							__SCREAMING_SNAKE_CASE      )		->    Optional[int]:







         """simple docstring"""



         a__    = len(__SCREAMING_SNAKE_CASE      )
         a__    = [0] * (
             4 * self.N
         )  # approximate the overall size of segment tree with array N
         self.build(1    ,							0    ,							self.N - 1      )



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE      )		->    Optional[Any]:







         """simple docstring"""



         return idx * 2



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE      )		->    Optional[int]:







         """simple docstring"""



         return idx * 2 + 1



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )		->    List[str]:  # noqa: E741







         """simple docstring"""



         if l == r:
             a__    = A[l]
         else:
             a__    = (l + r) // 2
             self.build(self.left(__SCREAMING_SNAKE_CASE      )    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )
             self.build(self.right(__SCREAMING_SNAKE_CASE      )    ,							mid + 1    ,							__SCREAMING_SNAKE_CASE      )
             a__    = max(self.st[self.left(__SCREAMING_SNAKE_CASE      )]    ,							self.st[self.right(__SCREAMING_SNAKE_CASE      )]      )



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )		->    int:







         """simple docstring"""



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



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )		->    Optional[int]:  # noqa: E741







         """simple docstring"""



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



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )		->    List[str]:







         """simple docstring"""



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



     def  lowercase__     (       self    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )		->    Any:  # noqa: E741







         """simple docstring"""



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




     def  lowercase__     (       self      )		->    List[Any]:







         """simple docstring"""



         a__    = []
         for i in range(1    ,							N + 1      ):
             show_list += [self.query(__SCREAMING_SNAKE_CASE    ,							__SCREAMING_SNAKE_CASE      )]
         print(__SCREAMING_SNAKE_CASE      )


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


