data_structures.binary_tree.segment_tree¶

Attributes¶

class data_structures.binary_tree.segment_tree.SegmentTree(a)¶

left(idx)¶

Returns the left child index for a given index in a binary tree.

>>> s = SegmentTree([1, 2, 3])
>>> s.left(1)
2
>>> s.left(2)
4

query(a, b)¶

Query the maximum value in the range [a,b].

>>> s = SegmentTree([1, 2, 3, 4, 5])
>>> s.query(1, 3)
3
>>> s.query(1, 5)
5

query_recursive(idx, left, right, a, b)¶: query(1, 1, N, a, b) for query max of [a,b]

right(idx)¶

Returns the right child index for a given index in a binary tree.

>>> s = SegmentTree([1, 2, 3])
>>> s.right(1)
3
>>> s.right(2)
5

update(a, b, val)¶

Update the values in the segment tree in the range [a,b] with the given value.

>>> s = SegmentTree([1, 2, 3, 4, 5])
>>> s.update(2, 4, 10)
True
>>> s.query(1, 5)
10

update_recursive(idx, left, right, a, b, val)¶: update(1, 1, N, a, b, v) for update val v to [a,b]