data_structures.binary_tree.segment_tree_other

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

arr

Classes

SegmentTree
SegmentTreeNode

Module Contents

class data_structures.binary_tree.segment_tree_other.SegmentTree(collection: collections.abc.Sequence, function)

>>> import operator
>>> num_arr = SegmentTree([2, 1, 5, 3, 4], operator.add)
>>> tuple(num_arr.traverse())  
(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())  
(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
>>>

_build_tree(start, end)

_query_range(node, i, j)

_update_tree(node, i, val)

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 >>>

traverse()

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

collection

fn

class data_structures.binary_tree.segment_tree_other.SegmentTreeNode(start, end, val, left=None, right=None)

__repr__()

end

left

mid

right

start

val

data_structures.binary_tree.segment_tree_other.arr