data_structures.binary_tree.persistent_segment_tree

Attributes

result

Classes

Node
PersistentSegmentTree

Module Contents

class data_structures.binary_tree.persistent_segment_tree.Node

left: Node | None = None

right: Node | None = None

value: int

class data_structures.binary_tree.persistent_segment_tree.PersistentSegmentTree(arr: list[int])

_build(arr: list[int], start: int, end: int) → Node

Builds a segment tree from the provided array.

>>> pst = PersistentSegmentTree([1, 2, 3, 4])
>>> root = pst._build([1, 2, 3, 4], 0, 3)
>>> root.value  # Sum of the whole array
10
>>> root.left.value  # Sum of the left half
3
>>> root.right.value  # Sum of the right half
7

_query(node: Node, start: int, end: int, left: int, right: int) → int

Queries the sum of values in the range [left, right] for the given node.

>>> pst = PersistentSegmentTree([1, 2, 3, 4])
>>> root = pst.roots[0]
>>> pst._query(root, 0, 3, 1, 2)  # Sum of elements at index 1 and 2
5
>>> pst._query(root, 0, 3, 0, 3)  # Sum of all elements
10
>>> pst._query(root, 0, 3, 2, 3)  # Sum of elements at index 2 and 3
7

_update(node: Node, start: int, end: int, index: int, value: int) → Node

Update the node for the specified index and value and return the new node.

>>> pst = PersistentSegmentTree([1, 2, 3, 4])
>>> old_root = pst.roots[0]
>>> new_root = pst._update(old_root, 0, 3, 1, 5)  # Update index 1 to 5
>>> new_root.value  # New sum after update
13
>>> old_root.value  # Old root remains unchanged
10
>>> new_root.left.value  # Updated left child
6
>>> new_root.right.value  # Right child remains the same
7

query(version: int, left: int, right: int) → int

Queries the sum in the given range for the specified version.

>>> pst = PersistentSegmentTree([1, 2, 3, 4])
>>> pst.query(0, 0, 3)  # Sum of all elements in original version
10
>>> pst.query(0, 1, 2)  # Sum of elements at index 1 and 2 in original version
5
>>> version_1 = pst.update(0, 1, 5)  # Update index 1 to 5
>>> pst.query(version_1, 0, 3)  # Sum of all elements in new version
13
>>> pst.query(version_1, 1, 2)  # Sum of elements at index 1 and 2
8

update(version: int, index: int, value: int) → int

Updates the value at the given index and returns the new version.

>>> pst = PersistentSegmentTree([1, 2, 3, 4])
>>> version_1 = pst.update(0, 1, 5)  # Update index 1 to 5
>>> pst.query(version_1, 0, 3)  # Query sum of all elements in new version
13
>>> pst.query(0, 0, 3)  # Original version remains unchanged
10
>>> version_2 = pst.update(version_1, 3, 6)  # Update index 3 to 6 in version_1
>>> pst.query(version_2, 0, 3)  # Query sum of all elements in newest version
15

n: int

roots: list[Node] = []

data_structures.binary_tree.persistent_segment_tree.result