data_structures.binary_tree.lazy_segment_tree
=============================================

.. py:module:: data_structures.binary_tree.lazy_segment_tree


Attributes
----------

.. autoapisummary::

   data_structures.binary_tree.lazy_segment_tree.A


Classes
-------

.. autoapisummary::

   data_structures.binary_tree.lazy_segment_tree.SegmentTree


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

.. py:class:: SegmentTree(size: int)

   .. py:method:: __str__() -> str


   .. py:method:: build(idx: int, left_element: int, right_element: int, a: list[int]) -> None


   .. py:method:: left(idx: int) -> int

      >>> segment_tree = SegmentTree(15)
      >>> segment_tree.left(1)
      2
      >>> segment_tree.left(2)
      4
      >>> segment_tree.left(12)
      24



   .. py:method:: query(idx: int, left_element: int, right_element: int, a: int, b: int) -> int | float

      query(1, 1, size, a, b) for query max of [a,b]
      >>> A = [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
      >>> segment_tree = SegmentTree(15)
      >>> segment_tree.build(1, 1, 15, A)
      >>> segment_tree.query(1, 1, 15, 4, 6)
      7
      >>> segment_tree.query(1, 1, 15, 7, 11)
      14
      >>> segment_tree.query(1, 1, 15, 7, 12)
      15



   .. py:method:: right(idx: int) -> int

      >>> segment_tree = SegmentTree(15)
      >>> segment_tree.right(1)
      3
      >>> segment_tree.right(2)
      5
      >>> segment_tree.right(12)
      25



   .. py:method:: update(idx: int, left_element: int, right_element: int, a: int, b: int, val: int) -> bool

      update with O(lg n) (Normal segment tree without lazy update will take O(nlg n)
      for each update)

      update(1, 1, size, a, b, v) for update val v to [a,b]



   .. py:attribute:: flag


   .. py:attribute:: lazy


   .. py:attribute:: segment_tree


   .. py:attribute:: size


.. py:data:: A