data_structures.binary_tree.wavelet_tree

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

test_array

Classes

Node

Functions

build_tree(→ Node | None)	Builds the tree for arr and returns the root
quantile(→ int)	Returns the index'th smallest element in interval [start, end] in the list
range_counting(→ int)	Returns the number of elements in range [start_num, end_num]
rank(→ int)	Returns the number of occurrences of num in interval [start, end] in the list
rank_till_index(→ int)	Returns the number of occurrences of num in interval [0, index] in the list

Module Contents

class data_structures.binary_tree.wavelet_tree.Node(length: int)

__repr__() → str

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

left: Node | None = None

map_left: list[int]

maxx: int = -1

minn: int = -1

right: Node | None = None

data_structures.binary_tree.wavelet_tree.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)

data_structures.binary_tree.wavelet_tree.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

data_structures.binary_tree.wavelet_tree.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

data_structures.binary_tree.wavelet_tree.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

data_structures.binary_tree.wavelet_tree.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

data_structures.binary_tree.wavelet_tree.test_array = [2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]