data_structures.binary_tree.non_recursive_segment_tree

A non-recursive Segment Tree implementation with range query and single element update, works virtually with any list of the same type of elements with a “commutative” combiner.

Explanation: https://www.geeksforgeeks.org/iterative-segment-tree-range-minimum-query/ https://www.geeksforgeeks.org/segment-tree-efficient-implementation/

>>> SegmentTree([1, 2, 3], lambda a, b: a + b).query(0, 2)
6
>>> SegmentTree([3, 1, 2], min).query(0, 2)
1
>>> SegmentTree([2, 3, 1], max).query(0, 2)
3
>>> st = SegmentTree([1, 5, 7, -1, 6], lambda a, b: a + b)
>>> st.update(1, -1)
>>> st.update(2, 3)
>>> st.query(1, 2)
2
>>> st.query(1, 1)
-1
>>> st.update(4, 1)
>>> st.query(3, 4)
0
>>> st = SegmentTree([[1, 2, 3], [3, 2, 1], [1, 1, 1]], lambda a, b: [a[i] + b[i] for i
...                                                                   in range(len(a))])
>>> st.query(0, 1)
[4, 4, 4]
>>> st.query(1, 2)
[4, 3, 2]
>>> st.update(1, [-1, -1, -1])
>>> st.query(1, 2)
[0, 0, 0]
>>> st.query(0, 2)
[1, 2, 3]

Attributes

T
test_array

Classes

SegmentTree

Module Contents

class data_structures.binary_tree.non_recursive_segment_tree.SegmentTree(arr: list[T], fnc: collections.abc.Callable[[T, T], T])

Bases: Generic[T]

build() → None

query(left: int, right: int) → T | None

Get range query value in log(N) time :param left: left element index :param right: right element index :return: element combined in the range [left, right]

>>> st = SegmentTree([1, 2, 3, 4], lambda a, b: a + b)
>>> st.query(0, 2)
6
>>> st.query(1, 2)
5
>>> st.query(0, 3)
10
>>> st.query(2, 3)
7

update(p: int, v: T) → None

Update an element in log(N) time :param p: position to be update :param v: new value

>>> st = SegmentTree([3, 1, 2, 4], min)
>>> st.query(0, 3)
1
>>> st.update(2, -1)
>>> st.query(0, 3)
-1

N: int

fn

st: list[T]

data_structures.binary_tree.non_recursive_segment_tree.T

data_structures.binary_tree.non_recursive_segment_tree.test_array