






from collections.abc import Sequence
from queue import Queue



class       __UpperCAmelCase		:







			def __init__(	self:  Optional[Any]      ,	UpperCAmelCase_:  str      ,	UpperCAmelCase_:  Union[str, Any]      ,	UpperCAmelCase_:  Optional[int]      ,	UpperCAmelCase_:  Optional[Any]=None      ,	UpperCAmelCase_:  Union[str, Any]=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:  Tuple     ):







									'''simple docstring'''




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



class       __UpperCAmelCase		:







			def __init__(	self:  Any      ,	UpperCAmelCase_:  Sequence      ,	UpperCAmelCase_:  Tuple     ):







									'''simple docstring'''




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







			def 							UpperCamelCase      (	self:  str      ,	UpperCAmelCase_:  Tuple      ,	UpperCAmelCase_:  str     ):







									'''simple docstring'''




									self._update_tree(self.root      ,	lowerCAmelCase_      ,	lowerCAmelCase_     )







			def 							UpperCamelCase      (	self:  List[Any]      ,	UpperCAmelCase_:  Tuple      ,	UpperCAmelCase_:  List[str]     ):







									'''simple docstring'''




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







			def 							UpperCamelCase      (	self:  Dict      ,	UpperCAmelCase_:  str      ,	UpperCAmelCase_:  Any     ):







									'''simple docstring'''




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







			def 							UpperCamelCase      (	self:  List[str]      ,	UpperCAmelCase_:  str      ,	UpperCAmelCase_:  List[Any]      ,	UpperCAmelCase_:  Tuple     ):







									'''simple docstring'''




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







			def 							UpperCamelCase      (	self:  int      ,	UpperCAmelCase_:  Dict      ,	UpperCAmelCase_:  Dict      ,	UpperCAmelCase_:  Optional[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      ,	lowerCAmelCase_      ,	lowerCAmelCase_     )
															else:
																					# range in left child tree and right child tree
																					return self.fn(
																					    self._query_range(node.left      ,	lowerCAmelCase_      ,	node.mid     )      ,	self._query_range(node.right      ,	node.mid + 1      ,	lowerCAmelCase_     )      ,	)
									else:
															# range in right child tree
															return self._query_range(node.right      ,	lowerCAmelCase_      ,	lowerCAmelCase_     )







			def 							UpperCamelCase      (	self:  str     ):







									'''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)
				UpperCamelCase 				=	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()








from timeit import timeit

def   a_    ( lowerCAmelCase_      :			int	):
   if number < 0:
      raise ValueError('the value of input must not be negative'	)
   __lowerCAmelCase								=	0
   while number:
      number &= number - 1
      result += 1
   return result

def   a_    ( lowerCAmelCase_      :			int	):
   if number < 0:
      raise ValueError('the value of input must not be negative'	)
   __lowerCAmelCase								=	0
   while number:
      if number % 2 == 1:
         result += 1
      number >>= 1
   return result

def   a_    ( ):

   def do_benchmark(lowerCAmelCase_      :			int	) -> None:
      __lowerCAmelCase								=	'import __main__ as z'
      print(F"""Benchmark when {number = }:"""	)
      print(F"""{get_set_bits_count_using_modulo_operator(lowerCAmelCase_	) = }"""	)
      __lowerCAmelCase								=	timeit('z.get_set_bits_count_using_modulo_operator(25)',	setup=lowerCAmelCase_	)
      print(F"""timeit() runs in {timing} seconds"""	)
      print(F"""{get_set_bits_count_using_brian_kernighans_algorithm(lowerCAmelCase_	) = }"""	)
      __lowerCAmelCase								=	timeit(
          'z.get_set_bits_count_using_brian_kernighans_algorithm(25)',	setup=lowerCAmelCase_,	)
      print(F"""timeit() runs in {timing} seconds"""	)

   for number in (25, 37, 58, 0):
      do_benchmark(lowerCAmelCase_	)
      print()


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     benchmark()

