data_structures.binary_tree.segment_tree_other
==============================================

.. py:module:: data_structures.binary_tree.segment_tree_other

.. autoapi-nested-parse::

   Segment_tree creates a segment tree with a given array and function,
   allowing queries to be done later in log(N) time
   function takes 2 values and returns a same type value



Attributes
----------

.. autoapisummary::

   data_structures.binary_tree.segment_tree_other.arr


Classes
-------

.. autoapisummary::

   data_structures.binary_tree.segment_tree_other.SegmentTree
   data_structures.binary_tree.segment_tree_other.SegmentTreeNode


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

.. py:class:: SegmentTree(collection: collections.abc.Sequence, function)

   >>> import operator
   >>> num_arr = SegmentTree([2, 1, 5, 3, 4], operator.add)
   >>> tuple(num_arr.traverse())  # doctest: +NORMALIZE_WHITESPACE
   (SegmentTreeNode(start=0, end=4, val=15),
       SegmentTreeNode(start=0, end=2, val=8),
       SegmentTreeNode(start=3, end=4, val=7),
       SegmentTreeNode(start=0, end=1, val=3),
       SegmentTreeNode(start=2, end=2, val=5),
       SegmentTreeNode(start=3, end=3, val=3),
       SegmentTreeNode(start=4, end=4, val=4),
       SegmentTreeNode(start=0, end=0, val=2),
       SegmentTreeNode(start=1, end=1, val=1))
   >>>
   >>> num_arr.update(1, 5)
   >>> tuple(num_arr.traverse())  # doctest: +NORMALIZE_WHITESPACE
   (SegmentTreeNode(start=0, end=4, val=19),
       SegmentTreeNode(start=0, end=2, val=12),
       SegmentTreeNode(start=3, end=4, val=7),
       SegmentTreeNode(start=0, end=1, val=7),
       SegmentTreeNode(start=2, end=2, val=5),
       SegmentTreeNode(start=3, end=3, val=3),
       SegmentTreeNode(start=4, end=4, val=4),
       SegmentTreeNode(start=0, end=0, val=2),
       SegmentTreeNode(start=1, end=1, val=5))
   >>>
   >>> num_arr.query_range(3, 4)
   7
   >>> num_arr.query_range(2, 2)
   5
   >>> num_arr.query_range(1, 3)
   13
   >>>
   >>> max_arr = SegmentTree([2, 1, 5, 3, 4], max)
   >>> for node in max_arr.traverse():
   ...     print(node)
   ...
   SegmentTreeNode(start=0, end=4, val=5)
   SegmentTreeNode(start=0, end=2, val=5)
   SegmentTreeNode(start=3, end=4, val=4)
   SegmentTreeNode(start=0, end=1, val=2)
   SegmentTreeNode(start=2, end=2, val=5)
   SegmentTreeNode(start=3, end=3, val=3)
   SegmentTreeNode(start=4, end=4, val=4)
   SegmentTreeNode(start=0, end=0, val=2)
   SegmentTreeNode(start=1, end=1, val=1)
   >>>
   >>> max_arr.update(1, 5)
   >>> for node in max_arr.traverse():
   ...     print(node)
   ...
   SegmentTreeNode(start=0, end=4, val=5)
   SegmentTreeNode(start=0, end=2, val=5)
   SegmentTreeNode(start=3, end=4, val=4)
   SegmentTreeNode(start=0, end=1, val=5)
   SegmentTreeNode(start=2, end=2, val=5)
   SegmentTreeNode(start=3, end=3, val=3)
   SegmentTreeNode(start=4, end=4, val=4)
   SegmentTreeNode(start=0, end=0, val=2)
   SegmentTreeNode(start=1, end=1, val=5)
   >>>
   >>> max_arr.query_range(3, 4)
   4
   >>> max_arr.query_range(2, 2)
   5
   >>> max_arr.query_range(1, 3)
   5
   >>>
   >>> min_arr = SegmentTree([2, 1, 5, 3, 4], min)
   >>> for node in min_arr.traverse():
   ...     print(node)
   ...
   SegmentTreeNode(start=0, end=4, val=1)
   SegmentTreeNode(start=0, end=2, val=1)
   SegmentTreeNode(start=3, end=4, val=3)
   SegmentTreeNode(start=0, end=1, val=1)
   SegmentTreeNode(start=2, end=2, val=5)
   SegmentTreeNode(start=3, end=3, val=3)
   SegmentTreeNode(start=4, end=4, val=4)
   SegmentTreeNode(start=0, end=0, val=2)
   SegmentTreeNode(start=1, end=1, val=1)
   >>>
   >>> min_arr.update(1, 5)
   >>> for node in min_arr.traverse():
   ...     print(node)
   ...
   SegmentTreeNode(start=0, end=4, val=2)
   SegmentTreeNode(start=0, end=2, val=2)
   SegmentTreeNode(start=3, end=4, val=3)
   SegmentTreeNode(start=0, end=1, val=2)
   SegmentTreeNode(start=2, end=2, val=5)
   SegmentTreeNode(start=3, end=3, val=3)
   SegmentTreeNode(start=4, end=4, val=4)
   SegmentTreeNode(start=0, end=0, val=2)
   SegmentTreeNode(start=1, end=1, val=5)
   >>>
   >>> min_arr.query_range(3, 4)
   3
   >>> min_arr.query_range(2, 2)
   5
   >>> min_arr.query_range(1, 3)
   3
   >>>


   .. py:method:: _build_tree(start, end)


   .. py:method:: _query_range(node, i, j)


   .. py:method:: _update_tree(node, i, val)


   .. py:method:: query_range(i, j)

      Get range query value in log(N) time
      :param i: left element index
      :param j: right element index
      :return: element combined in the range [i, j]
      >>> import operator
      >>> num_arr = SegmentTree([2, 1, 5, 3, 4], operator.add)
      >>> num_arr.update(1, 5)
      >>> num_arr.query_range(3, 4)
      7
      >>> num_arr.query_range(2, 2)
      5
      >>> num_arr.query_range(1, 3)
      13
      >>>



   .. py:method:: traverse()


   .. py:method:: update(i, val)

      Update an element in log(N) time
      :param i: position to be update
      :param val: new value
      >>> import operator
      >>> num_arr = SegmentTree([2, 1, 5, 3, 4], operator.add)
      >>> num_arr.update(1, 5)
      >>> num_arr.query_range(1, 3)
      13



   .. py:attribute:: collection


   .. py:attribute:: fn


.. py:class:: SegmentTreeNode(start, end, val, left=None, right=None)

   .. py:method:: __repr__()


   .. py:attribute:: end


   .. py:attribute:: left
      :value: None



   .. py:attribute:: mid


   .. py:attribute:: right
      :value: None



   .. py:attribute:: start


   .. py:attribute:: val


.. py:data:: arr