data_structures.binary_tree.lazy_segment_tree

Attributes

A

Classes

SegmentTree

Module Contents

class data_structures.binary_tree.lazy_segment_tree.SegmentTree(size: int)

__str__() → str

build(idx: int, left_element: int, right_element: int, a: list[int]) → None

left(idx: int) → int

>>> segment_tree = SegmentTree(15)
>>> segment_tree.left(1)
2
>>> segment_tree.left(2)
4
>>> segment_tree.left(12)
24

query(idx: int, left_element: int, right_element: int, a: int, b: int) → int | float

query(1, 1, size, a, b) for query max of [a,b] >>> A = [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8] >>> segment_tree = SegmentTree(15) >>> segment_tree.build(1, 1, 15, A) >>> segment_tree.query(1, 1, 15, 4, 6) 7 >>> segment_tree.query(1, 1, 15, 7, 11) 14 >>> segment_tree.query(1, 1, 15, 7, 12) 15

right(idx: int) → int

>>> segment_tree = SegmentTree(15)
>>> segment_tree.right(1)
3
>>> segment_tree.right(2)
5
>>> segment_tree.right(12)
25

update(idx: int, left_element: int, right_element: int, a: int, b: int, val: int) → bool

update with O(lg n) (Normal segment tree without lazy update will take O(nlg n) for each update)

update(1, 1, size, a, b, v) for update val v to [a,b]

flag

lazy

segment_tree

size

data_structures.binary_tree.lazy_segment_tree.A