


"""simple docstring"""




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowerCAmelCase	=							TypeVar('KT')
lowerCAmelCase	=							TypeVar('VT')


class 	_a							(      Generic[KT, VT]      ):

							def __init__(							self:     Tuple   ,						UpperCamelCase_:     KT | str = "root"   ,						UpperCamelCase_:     VT | None = None							)      ->       List[Any]:





									"""simple docstring"""







									lowercase__						=				key
									lowercase__						=				value
									lowercase__						=				[]

							def __repr__(							self:     Any							)      ->       Tuple:





									"""simple docstring"""







									return f'Node({self.key}: {self.value})'


							@property
							def 				lowerCamelCase_			(							self:     Dict							)      ->       Tuple:





									"""simple docstring"""







									return len(self.forward							)


class 	_a							(      Generic[KT, VT]      ):

							def __init__(							self:     Union[str, Any]   ,						UpperCamelCase_:     float = 0.5   ,						UpperCamelCase_:     int = 16							)      ->       str:





									"""simple docstring"""







									lowercase__						=				Node[KT, VT]()
									lowercase__						=				0
									lowercase__						=				p
									lowercase__						=				max_level

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





									"""simple docstring"""







									lowercase__						=				list(self							)

									if len(__SCREAMING_SNAKE_CASE							) == 0:
											return f'SkipList(level={self.level})'

									lowercase__						=				max((len(str(__SCREAMING_SNAKE_CASE							)							) for item in items)   ,						default=4							)
									lowercase__						=				max(__SCREAMING_SNAKE_CASE   ,						4							) + 4

									lowercase__						=				self.head
									lowercase__						=				[]

									lowercase__						=				node.forward.copy()
									lines.append(f'[{node.key}]'.ljust(__SCREAMING_SNAKE_CASE   ,						'''-'''							) + '''* ''' * len(__SCREAMING_SNAKE_CASE							)							)
									lines.append(''' ''' * label_size + '''| ''' * len(__SCREAMING_SNAKE_CASE							)							)

									while len(node.forward							) != 0:
											lowercase__						=				node.forward[0]

											lines.append(
											    f'[{node.key}]'.ljust(__SCREAMING_SNAKE_CASE   ,						'''-'''							)
											    + ''' '''.join(str(n.key							) if n.key == node.key else '''|''' for n in forwards							)							)
											lines.append(''' ''' * label_size + '''| ''' * len(__SCREAMING_SNAKE_CASE							)							)
											lowercase__						=				node.forward

									lines.append('''None'''.ljust(__SCREAMING_SNAKE_CASE							) + '''* ''' * len(__SCREAMING_SNAKE_CASE							)							)
									return f'SkipList(level={self.level})\n' + "\n".join(__SCREAMING_SNAKE_CASE							)

							def __iter__(							self:     List[str]							)      ->       Dict:





									"""simple docstring"""







									lowercase__						=				self.head

									while len(node.forward							) != 0:
											yield node.forward[0].key
											lowercase__						=				node.forward[0]

							def 				lowerCamelCase_			(							self:     Optional[int]							)      ->       int:





									"""simple docstring"""







									lowercase__						=				1
									while random() < self.p and level < self.max_level:
											level += 1

									return level

							def 				lowerCamelCase_			(							self:     List[str]   ,						UpperCamelCase_:     str							)      ->       List[str]:





									"""simple docstring"""







									lowercase__						=				[]

									lowercase__						=				self.head

									for i in reversed(range(self.level							)							):
											# i < node.level - When node level is lesser than `i` decrement `i`.
											# node.forward[i].key < key - Jumping to node with key value higher
											#                             or equal to searched key would result
											#                             in skipping searched key.
											while i < node.level and node.forward[i].key < key:
													lowercase__						=				node.forward[i]
											# Each leftmost node (relative to searched node) will potentially have to
											# be updated.
											update_vector.append(__SCREAMING_SNAKE_CASE							)

									update_vector.reverse()  # Note that we were inserting values in reverse order.

									# len(node.forward) != 0 - If current node doesn't contain any further
									#                          references then searched key is not present.
									# node.forward[0].key == key - Next node key should be equal to search key
									#                              if key is present.
									if len(node.forward							) != 0 and node.forward[0].key == key:
											return node.forward[0], update_vector
									else:
											return None, update_vector

							def 				lowerCamelCase_			(							self:     Optional[int]   ,						UpperCamelCase_:     KT							)      ->       List[Any]:





									"""simple docstring"""







									lowercase__					,		lowercase__						=				self._locate_node(__SCREAMING_SNAKE_CASE							)

									if node is not None:
											for i, update_node in enumerate(__SCREAMING_SNAKE_CASE							):
													# Remove or replace all references to removed node.
													if update_node.level > i and update_node.forward[i].key == key:
															if node.level > i:
																	lowercase__						=				node.forward[i]
															else:
																	lowercase__						=				update_node.forward[:i]

							def 				lowerCamelCase_			(							self:     Dict   ,						UpperCamelCase_:     KT   ,						UpperCamelCase_:     VT							)      ->       int:





									"""simple docstring"""







									lowercase__					,		lowercase__						=				self._locate_node(__SCREAMING_SNAKE_CASE							)
									if node is not None:
											lowercase__						=				value
									else:
											lowercase__						=				self.random_level()

											if level > self.level:
													# After level increase we have to add additional nodes to head.
													for _ in range(self.level - 1   ,						__SCREAMING_SNAKE_CASE							):
															update_vector.append(self.head							)
													lowercase__						=				level

											lowercase__						=				Node(__SCREAMING_SNAKE_CASE   ,						__SCREAMING_SNAKE_CASE							)

											for i, update_node in enumerate(update_vector[:level]							):
													# Change references to pass through new node.
													if update_node.level > i:
															new_node.forward.append(update_node.forward[i]							)

													if update_node.level < i + 1:
															update_node.forward.append(__SCREAMING_SNAKE_CASE							)
													else:
															lowercase__						=				new_node


							def 				lowerCamelCase_			(							self:     List[str]   ,						UpperCamelCase_:     VT							)      ->       Union[str, Any]:





									"""simple docstring"""







									lowercase__					,		lowercase__						=				self._locate_node(__SCREAMING_SNAKE_CASE							)

									if node is not None:
											return node.value

									return None
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()
		skip_list.insert('''Key1'''						,    3					)
		skip_list.insert('''Key2'''						,    12					)
		skip_list.insert('''Key3'''						,    41					)
		skip_list.insert('''Key4'''						,    -19					)

		lowercase__						=				skip_list.head
		lowercase__						=				{}
		while node.level != 0:
				lowercase__						=				node.forward[0]
				lowercase__						=				node.value

		assert len(lowercase__					) == 4
		assert all_values["Key1"] == 3
		assert all_values["Key2"] == 12
		assert all_values["Key3"] == 41
		assert all_values["Key4"] == -19
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()
		skip_list.insert('''Key1'''						,    10					)
		skip_list.insert('''Key1'''						,    12					)

		skip_list.insert('''Key5'''						,    7					)
		skip_list.insert('''Key7'''						,    10					)
		skip_list.insert('''Key10'''						,    5					)

		skip_list.insert('''Key7'''						,    7					)
		skip_list.insert('''Key5'''						,    5					)
		skip_list.insert('''Key10'''						,    10					)

		lowercase__						=				skip_list.head
		lowercase__						=				{}
		while node.level != 0:
				lowercase__						=				node.forward[0]
				lowercase__						=				node.value

		if len(lowercase__					) != 4:
				print()
		assert len(lowercase__					) == 4
		assert all_values["Key1"] == 12
		assert all_values["Key7"] == 7
		assert all_values["Key5"] == 5
		assert all_values["Key10"] == 10
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()
		assert skip_list.find('''Some key'''					) is None
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()

		skip_list.insert('''Key2'''						,    20					)
		assert skip_list.find('''Key2'''					) == 20

		skip_list.insert('''Some Key'''						,    10					)
		skip_list.insert('''Key2'''						,    8					)
		skip_list.insert('''V'''						,    13					)

		assert skip_list.find('''Y'''					) is None
		assert skip_list.find('''Key2'''					) == 8
		assert skip_list.find('''Some Key'''					) == 10
		assert skip_list.find('''V'''					) == 13
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()
		skip_list.delete('''Some key'''					)

		assert len(skip_list.head.forward					) == 0
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()

		skip_list.insert('''Key1'''						,    12					)
		skip_list.insert('''V'''						,    13					)
		skip_list.insert('''X'''						,    14					)
		skip_list.insert('''Key2'''						,    15					)

		skip_list.delete('''V'''					)
		skip_list.delete('''Key2'''					)

		assert skip_list.find('''V'''					) is None
		assert skip_list.find('''Key2'''					) is None
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()

		skip_list.insert('''Key1'''						,    12					)
		skip_list.insert('''V'''						,    13					)
		skip_list.insert('''X'''						,    14					)
		skip_list.insert('''Key2'''						,    15					)

		skip_list.delete('''V'''					)
		assert skip_list.find('''V'''					) is None
		assert skip_list.find('''X'''					) == 14
		assert skip_list.find('''Key1'''					) == 12
		assert skip_list.find('''Key2'''					) == 15

		skip_list.delete('''X'''					)
		assert skip_list.find('''V'''					) is None
		assert skip_list.find('''X'''					) is None
		assert skip_list.find('''Key1'''					) == 12
		assert skip_list.find('''Key2'''					) == 15

		skip_list.delete('''Key1'''					)
		assert skip_list.find('''V'''					) is None
		assert skip_list.find('''X'''					) is None
		assert skip_list.find('''Key1'''					) is None
		assert skip_list.find('''Key2'''					) == 15

		skip_list.delete('''Key2'''					)
		assert skip_list.find('''V'''					) is None
		assert skip_list.find('''X'''					) is None
		assert skip_list.find('''Key1'''					) is None
		assert skip_list.find('''Key2'''					) is None
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()

		skip_list.insert('''Key1'''						,    12					)
		skip_list.insert('''V'''						,    13					)
		skip_list.insert('''X'''						,    1_42					)
		skip_list.insert('''Key2'''						,    15					)

		skip_list.delete('''X'''					)

		def traverse_keys(SCREAMING_SNAKE_CASE					):
				yield node.key
				for forward_node in node.forward:
						yield from traverse_keys(lowercase__					)

		assert len(set(traverse_keys(skip_list.head					)					)					) == 4
def       _a			(				):


		"""simple docstring"""




		def is_sorted(SCREAMING_SNAKE_CASE					):
				return all(next_item >= item for item, next_item in zip(lowercase__						,    lst[1:]					)					)

		lowercase__						=				SkipList()
		for i in range(10					):
				skip_list.insert(lowercase__						,    lowercase__					)
		assert is_sorted(list(lowercase__					)					)
		skip_list.delete(5					)
		skip_list.delete(8					)
		skip_list.delete(2					)
		assert is_sorted(list(lowercase__					)					)
		skip_list.insert(-12						,    -12					)
		skip_list.insert(77						,    77					)
		assert is_sorted(list(lowercase__					)					)
def       _a			(				):


		"""simple docstring"""




		for _ in range(1_00					):
				# Repeat test 100 times due to the probabilistic nature of skip list
				# random values == random bugs
				test_insert()
				test_insert_overrides_existing_value()

				test_searching_empty_list_returns_none()
				test_search()

				test_deleting_item_from_empty_list_do_nothing()
				test_deleted_items_are_not_founded_by_find_method()
				test_delete_removes_only_given_key()
				test_delete_doesnt_leave_dead_nodes()

				test_iter_always_yields_sorted_values()
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				SkipList()
		skip_list.insert(2						,    '''2'''					)
		skip_list.insert(4						,    '''4'''					)
		skip_list.insert(6						,    '''4'''					)
		skip_list.insert(4						,    '''5'''					)
		skip_list.insert(8						,    '''4'''					)
		skip_list.insert(9						,    '''4'''					)

		skip_list.delete(4					)

		print(lowercase__					)


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()






from collections.abc import Sequence
from queue import Queue


class 	_a							:

							def __init__(							self:     Tuple   ,						UpperCamelCase_:     Optional[int]   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     Optional[Any]   ,						UpperCamelCase_:     Union[str, Any]=None   ,						UpperCamelCase_:     Dict=None							)      ->       Tuple:





									"""simple docstring"""







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


							def __repr__(							self:     Optional[int]							)      ->       Optional[Any]:





									"""simple docstring"""







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


class 	_a							:

							def __init__(							self:     Any   ,						UpperCamelCase_:     Sequence   ,						UpperCamelCase_:     Any							)      ->       List[str]:





									"""simple docstring"""







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

							def 				lowerCamelCase_			(							self:     int   ,						UpperCamelCase_:     Union[str, Any]   ,						UpperCamelCase_:     Union[str, Any]							)      ->       Union[str, Any]:





									"""simple docstring"""







									self._update_tree(self.root   ,						UpperCamelCase_   ,						UpperCamelCase_							)

							def 				lowerCamelCase_			(							self:     str   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     List[str]							)      ->       Optional[Any]:





									"""simple docstring"""







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

							def 				lowerCamelCase_			(							self:     List[str]   ,						UpperCamelCase_:     Tuple   ,						UpperCamelCase_:     Dict							)      ->       str:





									"""simple docstring"""







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

							def 				lowerCamelCase_			(							self:     List[Any]   ,						UpperCamelCase_:     Dict   ,						UpperCamelCase_:     Tuple   ,						UpperCamelCase_:     Union[str, Any]							)      ->       Dict:





									"""simple docstring"""







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

							def 				lowerCamelCase_			(							self:     List[Any]   ,						UpperCamelCase_:     str   ,						UpperCamelCase_:     Dict   ,						UpperCamelCase_:     Dict							)      ->       List[Any]:





									"""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   ,						UpperCamelCase_   ,						UpperCamelCase_							)
											else:
													# range in left child tree and right child tree
													return self.fn(
													    self._query_range(node.left   ,						UpperCamelCase_   ,						node.mid							)   ,						self._query_range(node.right   ,						node.mid + 1   ,						UpperCamelCase_							)   ,						)
									else:
											# range in right child tree
											return self._query_range(node.right   ,						UpperCamelCase_   ,						UpperCamelCase_							)


							def 				lowerCamelCase_			(							self:     Optional[int]							)      ->       str:





									"""simple docstring"""







									if self.root is not None:
											lowercase__						=				Queue()
											queue.put(self.root							)
											while not queue.empty():
													lowercase__						=				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()


