data_structures.binary_tree.wavelet_tree
========================================

.. py:module:: data_structures.binary_tree.wavelet_tree

.. autoapi-nested-parse::

   Wavelet tree is a data-structure designed to efficiently answer various range queries
   for arrays. Wavelets trees are different from other binary trees in the sense that
   the nodes are split based on the actual values of the elements and not on indices,
   such as the with segment trees or fenwick trees. You can read more about them here:
   1. https://users.dcc.uchile.cl/~jperez/papers/ioiconf16.pdf
   2. https://www.youtube.com/watch?v=4aSv9PcecDw&t=811s
   3. https://www.youtube.com/watch?v=CybAgVF-MMc&t=1178s



Attributes
----------

.. autoapisummary::

   data_structures.binary_tree.wavelet_tree.test_array


Classes
-------

.. autoapisummary::

   data_structures.binary_tree.wavelet_tree.Node


Functions
---------

.. autoapisummary::

   data_structures.binary_tree.wavelet_tree.build_tree
   data_structures.binary_tree.wavelet_tree.quantile
   data_structures.binary_tree.wavelet_tree.range_counting
   data_structures.binary_tree.wavelet_tree.rank
   data_structures.binary_tree.wavelet_tree.rank_till_index


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

.. py:class:: Node(length: int)

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

      >>> node = Node(length=27)
      >>> repr(node)
      'Node(min_value=-1 max_value=-1)'
      >>> repr(node) == str(node)
      True



   .. py:attribute:: left
      :type:  Node | None
      :value: None



   .. py:attribute:: map_left
      :type:  list[int]


   .. py:attribute:: maxx
      :type:  int
      :value: -1



   .. py:attribute:: minn
      :type:  int
      :value: -1



   .. py:attribute:: right
      :type:  Node | None
      :value: None



.. py:function:: build_tree(arr: list[int]) -> Node | None

   Builds the tree for arr and returns the root
   of the constructed tree

   >>> build_tree(test_array)
   Node(min_value=0 max_value=9)


.. py:function:: quantile(node: Node | None, index: int, start: int, end: int) -> int

   Returns the index'th smallest element in interval [start, end] in the list
   index is 0-indexed

   >>> root = build_tree(test_array)
   >>> quantile(root, 2, 2, 5)
   5
   >>> quantile(root, 5, 2, 13)
   4
   >>> quantile(root, 0, 6, 6)
   8
   >>> quantile(root, 4, 2, 5)
   -1


.. py:function:: range_counting(node: Node | None, start: int, end: int, start_num: int, end_num: int) -> int

   Returns the number of elements in range [start_num, end_num]
   in interval [start, end] in the list

   >>> root = build_tree(test_array)
   >>> range_counting(root, 1, 10, 3, 7)
   3
   >>> range_counting(root, 2, 2, 1, 4)
   1
   >>> range_counting(root, 0, 19, 0, 100)
   20
   >>> range_counting(root, 1, 0, 1, 100)
   0
   >>> range_counting(root, 0, 17, 100, 1)
   0


.. py:function:: rank(node: Node | None, num: int, start: int, end: int) -> int

   Returns the number of occurrences of num in interval [start, end] in the list

   >>> root = build_tree(test_array)
   >>> rank(root, 6, 3, 13)
   2
   >>> rank(root, 2, 0, 19)
   4
   >>> rank(root, 9, 2 ,2)
   0
   >>> rank(root, 0, 5, 10)
   2


.. py:function:: rank_till_index(node: Node | None, num: int, index: int) -> int

   Returns the number of occurrences of num in interval [0, index] in the list

   >>> root = build_tree(test_array)
   >>> rank_till_index(root, 6, 6)
   1
   >>> rank_till_index(root, 2, 0)
   1
   >>> rank_till_index(root, 1, 10)
   2
   >>> rank_till_index(root, 17, 7)
   0
   >>> rank_till_index(root, 0, 9)
   1


.. py:data:: test_array
   :value: [2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]