
"""simple docstring"""




import json
import os
import tempfile
from unittest.mock import patch

import torch
from torch.utils.data import DataLoader, TensorDataset

from accelerate import DistributedType, infer_auto_device_map, init_empty_weights
from accelerate.accelerator import Accelerator
from accelerate.state import GradientState, PartialState
from accelerate.test_utils import require_bnb, require_multi_gpu, slow
from accelerate.test_utils.testing import AccelerateTestCase, require_cuda
from accelerate.utils import patch_environment



def        _lowerCamelCase ( ):
		SCREAMING_SNAKE_CASE_						 = torch.nn.Linear(2,							4    )
		SCREAMING_SNAKE_CASE_						 = torch.optim.AdamW(model.parameters(),							lr=1.0    )
		SCREAMING_SNAKE_CASE_						 = torch.optim.lr_scheduler.OneCycleLR(__a,							max_lr=0.0_1,							steps_per_epoch=2,							epochs=1    )
		SCREAMING_SNAKE_CASE_						 = DataLoader(TensorDataset(torch.tensor([1, 2, 3]    )    )    )
		SCREAMING_SNAKE_CASE_						 = DataLoader(TensorDataset(torch.tensor([4, 5, 6]    )    )    )

		return model, optimizer, scheduler, train_dl, valid_dl



def        _lowerCamelCase ( __a    ):
		return (model.weight.abs().sum() + model.bias.abs().sum()).item()



def        _lowerCamelCase ( __a    ):
		SCREAMING_SNAKE_CASE_						 = torch.nn.Linear(*tuple(model.weight.T.shape    )    ).state_dict()
		model.load_state_dict(__a    )





class  snake_case     (							__lowercase   ):

							@require_cuda
							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									assert PartialState._shared_state["_cpu"] is False
									assert PartialState._shared_state["device"].type == "cuda"
									with self.assertRaises(SCREAMING_SNAKE_CASE_    ):
											SCREAMING_SNAKE_CASE_						 = Accelerator(cpu=SCREAMING_SNAKE_CASE_    )

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_						 = GradientState()
									assert state.num_steps == 1
									SCREAMING_SNAKE_CASE_						 = 4
									assert state.num_steps == 4

									assert state.sync_gradients is True
									SCREAMING_SNAKE_CASE_						 = False
									assert state.sync_gradients is False
									GradientState._reset_state()

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = create_components()

									(
									    (
									    SCREAMING_SNAKE_CASE_
									) ,(
									    SCREAMING_SNAKE_CASE_
									) ,(
									    SCREAMING_SNAKE_CASE_
									) ,(
									    SCREAMING_SNAKE_CASE_
									) ,(
									    SCREAMING_SNAKE_CASE_
									) ,
									)						 = accelerator.prepare(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

									self.assertTrue(prepared_model in accelerator._models    )
									self.assertTrue(prepared_optimizer in accelerator._optimizers    )
									self.assertTrue(prepared_scheduler in accelerator._schedulers    )
									self.assertTrue(prepared_train_dl in accelerator._dataloaders    )
									self.assertTrue(prepared_valid_dl in accelerator._dataloaders    )

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = create_components()
									accelerator.prepare(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									accelerator.free_memory()

									self.assertTrue(len(accelerator._models    ) == 0    )
									self.assertTrue(len(accelerator._optimizers    ) == 0    )
									self.assertTrue(len(accelerator._schedulers    ) == 0    )
									self.assertTrue(len(accelerator._dataloaders    ) == 0    )

							def _lowercase					(self    ):

									"""simple docstring"""







									PartialState._reset_state()

									# Mock torch.cuda.set_device to avoid an exception as the device doesn't exist
									def noop(*SCREAMING_SNAKE_CASE_       ,       **SCREAMING_SNAKE_CASE_    ):
											pass

									with patch('''torch.cuda.set_device'''       ,       SCREAMING_SNAKE_CASE_    ), patch_environment(ACCELERATE_TORCH_DEVICE='''cuda:64'''    ):
											SCREAMING_SNAKE_CASE_						 = Accelerator()
											self.assertEqual(str(accelerator.state.device    )       ,       '''cuda:64'''    )

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = create_components()
									accelerator.prepare(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

									SCREAMING_SNAKE_CASE_						 = get_signature(SCREAMING_SNAKE_CASE_    )

									with tempfile.TemporaryDirectory() as tmpdirname:
											accelerator.save_state(SCREAMING_SNAKE_CASE_    )

											# make sure random weights don't match
											load_random_weights(SCREAMING_SNAKE_CASE_    )
											self.assertTrue(abs(model_signature - get_signature(SCREAMING_SNAKE_CASE_    )    ) > 1e-3    )

											# make sure loaded weights match
											accelerator.load_state(SCREAMING_SNAKE_CASE_    )
											self.assertTrue(abs(model_signature - get_signature(SCREAMING_SNAKE_CASE_    )    ) < 1e-3    )

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = create_components()
									accelerator.prepare(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

									SCREAMING_SNAKE_CASE_						 = get_signature(SCREAMING_SNAKE_CASE_    )

									# saving hook
									def save_config(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):
											SCREAMING_SNAKE_CASE_						 = {'''class_name''': models[0].__class__.__name__}

											with open(os.path.join(SCREAMING_SNAKE_CASE_       ,       '''data.json'''    )       ,       '''w'''    ) as f:
													json.dump(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

        # loading hook
									def load_config(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):
											with open(os.path.join(SCREAMING_SNAKE_CASE_       ,       '''data.json'''    )       ,       '''r'''    ) as f:
													SCREAMING_SNAKE_CASE_						 = json.load(SCREAMING_SNAKE_CASE_    )

											SCREAMING_SNAKE_CASE_						 = config['''class_name''']

									SCREAMING_SNAKE_CASE_						 = accelerator.register_save_state_pre_hook(SCREAMING_SNAKE_CASE_    )
									SCREAMING_SNAKE_CASE_						 = accelerator.register_load_state_pre_hook(SCREAMING_SNAKE_CASE_    )

									with tempfile.TemporaryDirectory() as tmpdirname:
											accelerator.save_state(SCREAMING_SNAKE_CASE_    )

											# make sure random weights don't match with hooks
											load_random_weights(SCREAMING_SNAKE_CASE_    )
											self.assertTrue(abs(model_signature - get_signature(SCREAMING_SNAKE_CASE_    )    ) > 1e-3    )

											# random class name to verify correct one is loaded
											SCREAMING_SNAKE_CASE_						 = '''random'''

											# make sure loaded weights match with hooks
											accelerator.load_state(SCREAMING_SNAKE_CASE_    )
											self.assertTrue(abs(model_signature - get_signature(SCREAMING_SNAKE_CASE_    )    ) < 1e-3    )

											# mode.class_name is loaded from config
											self.assertTrue(model.class_name == model.__class__.__name__    )

									# remove hooks
									save_hook.remove()
									load_hook.remove()

									with tempfile.TemporaryDirectory() as tmpdirname:
											accelerator.save_state(SCREAMING_SNAKE_CASE_    )

											# make sure random weights don't match with hooks removed
											load_random_weights(SCREAMING_SNAKE_CASE_    )
											self.assertTrue(abs(model_signature - get_signature(SCREAMING_SNAKE_CASE_    )    ) > 1e-3    )

											# random class name to verify correct one is loaded
											SCREAMING_SNAKE_CASE_						 = '''random'''

											# make sure loaded weights match with hooks removed
											accelerator.load_state(SCREAMING_SNAKE_CASE_    )
											self.assertTrue(abs(model_signature - get_signature(SCREAMING_SNAKE_CASE_    )    ) < 1e-3    )

											# mode.class_name is NOT loaded from config
											self.assertTrue(model.class_name != model.__class__.__name__    )

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = create_components()
									SCREAMING_SNAKE_CASE_						 = None

									# This should work
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = accelerator.prepare(
									    SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									self.assertTrue(dummy_obj is None    )

							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = Accelerator()
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = create_components()
									SCREAMING_SNAKE_CASE_						 = [1, 2, 3]

									# This should work
									SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_						 = accelerator.prepare(
									    SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									self.assertEqual(
									    getattr(SCREAMING_SNAKE_CASE_       ,       '''_is_accelerate_prepared'''       ,       SCREAMING_SNAKE_CASE_    )       ,       SCREAMING_SNAKE_CASE_       ,       '''Dummy object should have `_is_accelerate_prepared` set to `True`'''       ,       )
									self.assertEqual(
									    getattr(SCREAMING_SNAKE_CASE_       ,       '''_is_accelerate_prepared'''       ,       SCREAMING_SNAKE_CASE_    )       ,       SCREAMING_SNAKE_CASE_       ,       '''Model is missing `_is_accelerator_prepared` or is set to `False`'''       ,       )
									self.assertEqual(
									    getattr(SCREAMING_SNAKE_CASE_       ,       '''_is_accelerate_prepared'''       ,       SCREAMING_SNAKE_CASE_    )       ,       SCREAMING_SNAKE_CASE_       ,       '''Optimizer is missing `_is_accelerator_prepared` or is set to `False`'''       ,       )
									self.assertEqual(
									    getattr(SCREAMING_SNAKE_CASE_       ,       '''_is_accelerate_prepared'''       ,       SCREAMING_SNAKE_CASE_    )       ,       SCREAMING_SNAKE_CASE_       ,       '''Scheduler is missing `_is_accelerator_prepared` or is set to `False`'''       ,       )
									self.assertEqual(
									    getattr(SCREAMING_SNAKE_CASE_       ,       '''_is_accelerate_prepared'''       ,       SCREAMING_SNAKE_CASE_    )       ,       SCREAMING_SNAKE_CASE_       ,       '''Train Dataloader is missing `_is_accelerator_prepared` or is set to `False`'''       ,       )
									self.assertEqual(
									    getattr(SCREAMING_SNAKE_CASE_       ,       '''_is_accelerate_prepared'''       ,       SCREAMING_SNAKE_CASE_    )       ,       SCREAMING_SNAKE_CASE_       ,       '''Valid Dataloader is missing `_is_accelerator_prepared` or is set to `False`'''       ,       )

							@slow
							@require_bnb
							def _lowercase					(self    ):

									"""simple docstring"""







									from transformers import AutoModelForCausalLM

									SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
									    '''EleutherAI/gpt-neo-125m'''       ,       load_in_abit=SCREAMING_SNAKE_CASE_       ,       device_map={'''''': 0}       ,       )
									SCREAMING_SNAKE_CASE_						 = Accelerator()

									# This should work
									SCREAMING_SNAKE_CASE_						 = accelerator.prepare(SCREAMING_SNAKE_CASE_    )

							@slow
							@require_bnb
							def _lowercase					(self    ):

									"""simple docstring"""







									from transformers import AutoModelForCausalLM

									SCREAMING_SNAKE_CASE_						 = Accelerator()

									with init_empty_weights():
											SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
											    '''EleutherAI/gpt-neo-125m'''       ,       )
											model.tie_weights()
											SCREAMING_SNAKE_CASE_						 = infer_auto_device_map(SCREAMING_SNAKE_CASE_    )
											SCREAMING_SNAKE_CASE_						 = '''cpu'''

									SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
									    '''EleutherAI/gpt-neo-125m'''       ,       device_map=SCREAMING_SNAKE_CASE_       ,       load_in_abit=SCREAMING_SNAKE_CASE_       ,       llm_inta_enable_fpaa_cpu_offload=SCREAMING_SNAKE_CASE_    )

									# This should not work and get value error
									with self.assertRaises(SCREAMING_SNAKE_CASE_    ):
											SCREAMING_SNAKE_CASE_						 = accelerator.prepare(SCREAMING_SNAKE_CASE_    )

							@slow
							@require_bnb
							@require_multi_gpu
							def _lowercase					(self    ):

									"""simple docstring"""







									from transformers import AutoModelForCausalLM

									SCREAMING_SNAKE_CASE_						 = {'''distributed_type''': DistributedType.MULTI_GPU}

									with init_empty_weights():
											SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
											    '''EleutherAI/gpt-neo-125m'''       ,       )
											model.tie_weights()
											SCREAMING_SNAKE_CASE_						 = infer_auto_device_map(SCREAMING_SNAKE_CASE_    )
											SCREAMING_SNAKE_CASE_						 = 1

									SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
									    '''EleutherAI/gpt-neo-125m'''       ,       load_in_abit=SCREAMING_SNAKE_CASE_       ,       device_map=SCREAMING_SNAKE_CASE_       ,       )
									SCREAMING_SNAKE_CASE_						 = Accelerator()

									# This should not work and get value error
									with self.assertRaises(SCREAMING_SNAKE_CASE_    ):
											SCREAMING_SNAKE_CASE_						 = accelerator.prepare(SCREAMING_SNAKE_CASE_    )

									PartialState._reset_state()

							@slow
							@require_bnb
							@require_multi_gpu
							def _lowercase					(self    ):

									"""simple docstring"""







									from transformers import AutoModelForCausalLM

									with init_empty_weights():
											SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
											    '''EleutherAI/gpt-neo-125m'''       ,       )
											SCREAMING_SNAKE_CASE_						 = infer_auto_device_map(SCREAMING_SNAKE_CASE_    )
											SCREAMING_SNAKE_CASE_						 = 1

									SCREAMING_SNAKE_CASE_						 = AutoModelForCausalLM.from_pretrained(
									    '''EleutherAI/gpt-neo-125m'''       ,       load_in_abit=SCREAMING_SNAKE_CASE_       ,       device_map=SCREAMING_SNAKE_CASE_       ,       )
									SCREAMING_SNAKE_CASE_						 = Accelerator()

									# This should work
									SCREAMING_SNAKE_CASE_						 = accelerator.prepare(SCREAMING_SNAKE_CASE_    )







							@require_cuda
							def _lowercase					(self    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = torch.nn.Linear(10       ,       10    )
									SCREAMING_SNAKE_CASE_						 = torch.optim.SGD(model.parameters()       ,       lr=0.01    )
									SCREAMING_SNAKE_CASE_						 = Accelerator(cpu=SCREAMING_SNAKE_CASE_    )
									SCREAMING_SNAKE_CASE_						 = accelerator.prepare(SCREAMING_SNAKE_CASE_    )

"""simple docstring"""




from collections.abc import Sequence
from queue import Queue





class  snake_case     :

							def __init__(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_=None       ,       SCREAMING_SNAKE_CASE_=None    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = start
									SCREAMING_SNAKE_CASE_						 = end
									SCREAMING_SNAKE_CASE_						 = val
									SCREAMING_SNAKE_CASE_						 = (start + end) // 2
									SCREAMING_SNAKE_CASE_						 = left
									SCREAMING_SNAKE_CASE_						 = right







							def __repr__(self    ):

									"""simple docstring"""







									return f'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'







class  snake_case     :

							def __init__(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = collection
									SCREAMING_SNAKE_CASE_						 = function
									if self.collection:
											SCREAMING_SNAKE_CASE_						 = self._build_tree(0       ,       len(SCREAMING_SNAKE_CASE_    ) - 1    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									self._update_tree(self.root       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									return self._query_range(self.root       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									if start == end:
											return SegmentTreeNode(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       self.collection[start]    )
									SCREAMING_SNAKE_CASE_						 = (start + end) // 2
									SCREAMING_SNAKE_CASE_						 = self._build_tree(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									SCREAMING_SNAKE_CASE_						 = self._build_tree(mid + 1       ,       SCREAMING_SNAKE_CASE_    )
									return SegmentTreeNode(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       self.fn(left.val       ,       right.val    )       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									if node.start == i and node.end == i:
											SCREAMING_SNAKE_CASE_						 = val
											return
									if i <= node.mid:
											self._update_tree(node.left       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									else:
											self._update_tree(node.right       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									SCREAMING_SNAKE_CASE_						 = self.fn(node.left.val       ,       node.right.val    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									if node.start == i and node.end == j:
											return node.val

									if i <= node.mid:
											if j <= node.mid:
													# range in left child tree
													return self._query_range(node.left       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
											else:
													# range in left child tree and right child tree
													return self.fn(
													    self._query_range(node.left       ,       SCREAMING_SNAKE_CASE_       ,       node.mid    )       ,       self._query_range(node.right       ,       node.mid + 1       ,       SCREAMING_SNAKE_CASE_    )       ,       )
									else:
											# range in right child tree
											return self._query_range(node.right       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )







							def _lowercase					(self    ):

									"""simple docstring"""







									if self.root is not None:
											SCREAMING_SNAKE_CASE_						 = Queue()
											queue.put(self.root    )
											while not queue.empty():
													SCREAMING_SNAKE_CASE_						 = queue.get()
													yield node

													if node.left is not None:
															queue.put(node.left    )

													if node.right is not None:
															queue.put(node.right    )


if __name__ == "__main__":
						import operator

						for fn in [operator.add, max, min]:
												print('*' * 50)
												lowerCAmelCase__							=				SegmentTree([2, 1, 5, 3, 4], fn)
												for node in arr.traverse():
																		print(node)
												print()

												arr.update(1, 5)
												for node in arr.traverse():
																		print(node)
												print()

												print(arr.query_range(3, 4))  # 7
												print(arr.query_range(2, 2))  # 5
												print(arr.query_range(1, 3))  # 13
												print()