data_structures.binary_tree.non_recursive_segment_tree
======================================================

.. py:module:: data_structures.binary_tree.non_recursive_segment_tree

.. autoapi-nested-parse::

   A non-recursive Segment Tree implementation with range query and single element update,
   works virtually with any list of the same type of elements with a "commutative"
   combiner.

   Explanation:
   https://www.geeksforgeeks.org/iterative-segment-tree-range-minimum-query/
   https://www.geeksforgeeks.org/segment-tree-efficient-implementation/

   >>> SegmentTree([1, 2, 3], lambda a, b: a + b).query(0, 2)
   6
   >>> SegmentTree([3, 1, 2], min).query(0, 2)
   1
   >>> SegmentTree([2, 3, 1], max).query(0, 2)
   3
   >>> st = SegmentTree([1, 5, 7, -1, 6], lambda a, b: a + b)
   >>> st.update(1, -1)
   >>> st.update(2, 3)
   >>> st.query(1, 2)
   2
   >>> st.query(1, 1)
   -1
   >>> st.update(4, 1)
   >>> st.query(3, 4)
   0
   >>> st = SegmentTree([[1, 2, 3], [3, 2, 1], [1, 1, 1]], lambda a, b: [a[i] + b[i] for i
   ...                                                                   in range(len(a))])
   >>> st.query(0, 1)
   [4, 4, 4]
   >>> st.query(1, 2)
   [4, 3, 2]
   >>> st.update(1, [-1, -1, -1])
   >>> st.query(1, 2)
   [0, 0, 0]
   >>> st.query(0, 2)
   [1, 2, 3]



Attributes
----------

.. autoapisummary::

   data_structures.binary_tree.non_recursive_segment_tree.T
   data_structures.binary_tree.non_recursive_segment_tree.test_array


Classes
-------

.. autoapisummary::

   data_structures.binary_tree.non_recursive_segment_tree.SegmentTree


Module Contents
---------------

.. py:class:: SegmentTree(arr: list[T], fnc: collections.abc.Callable[[T, T], T])

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ ]


   .. py:method:: build() -> None


   .. py:method:: query(left: int, right: int) -> T | None

      Get range query value in log(N) time
      :param left: left element index
      :param right: right element index
      :return: element combined in the range [left, right]

      >>> st = SegmentTree([1, 2, 3, 4], lambda a, b: a + b)
      >>> st.query(0, 2)
      6
      >>> st.query(1, 2)
      5
      >>> st.query(0, 3)
      10
      >>> st.query(2, 3)
      7



   .. py:method:: update(p: int, v: T) -> None

      Update an element in log(N) time
      :param p: position to be update
      :param v: new value

      >>> st = SegmentTree([3, 1, 2, 4], min)
      >>> st.query(0, 3)
      1
      >>> st.update(2, -1)
      >>> st.query(0, 3)
      -1



   .. py:attribute:: N
      :type:  int


   .. py:attribute:: fn


   .. py:attribute:: st
      :type:  list[T]


.. py:data:: T

.. py:data:: test_array