data_structures.binary_tree.maximum_fenwick_tree
================================================

.. py:module:: data_structures.binary_tree.maximum_fenwick_tree


Classes
-------

.. autoapisummary::

   data_structures.binary_tree.maximum_fenwick_tree.MaxFenwickTree


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

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

   Maximum Fenwick Tree

   More info: https://cp-algorithms.com/data_structures/fenwick.html
   ---------
   >>> ft = MaxFenwickTree(5)
   >>> ft.query(0, 5)
   0
   >>> ft.update(4, 100)
   >>> ft.query(0, 5)
   100
   >>> ft.update(4, 0)
   >>> ft.update(2, 20)
   >>> ft.query(0, 5)
   20
   >>> ft.update(4, 10)
   >>> ft.query(2, 5)
   20
   >>> ft.query(1, 5)
   20
   >>> ft.update(2, 0)
   >>> ft.query(0, 5)
   10
   >>> ft = MaxFenwickTree(10000)
   >>> ft.update(255, 30)
   >>> ft.query(0, 10000)
   30
   >>> ft = MaxFenwickTree(6)
   >>> ft.update(5, 1)
   >>> ft.query(5, 6)
   1
   >>> ft = MaxFenwickTree(6)
   >>> ft.update(0, 1000)
   >>> ft.query(0, 1)
   1000


   .. py:method:: get_next(index: int) -> int
      :staticmethod:


      Get next index in O(1)



   .. py:method:: get_prev(index: int) -> int
      :staticmethod:


      Get previous index in O(1)



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

      Answer the query of maximum range [l, r) in O(lg^2 N)

      Parameters:
          left: left index of query range (inclusive)
          right: right index of query range (exclusive)

      Returns:
          Maximum value of range [left, right)



   .. py:method:: update(index: int, value: int) -> None

      Set index to value in O(lg^2 N)

      Parameters:
          index: index to update
          value: value to set

      Returns:
          None



   .. py:attribute:: arr


   .. py:attribute:: size


   .. py:attribute:: tree