Persistent Segment Tree Operations
Persistent Segment Trees allow you to perform updates and queries efficiently while preserving the history of changes. Here are the primary operations you can perform on a Persistent Segment Tree:
- Build: Construct the initial segment tree from an array.
- Update: Create a new version of the tree with an updated value at a specific index.
- Query: Perform range queries on any version of the tree.
1. Building the Initial Segment Tree
The build
function constructs the segment tree from an array. This is similar to building a regular segment tree but sets up the foundation for persistence.
Algorithm:
- If the current segment is a single element (i.e.,
left == right
), create a leaf node with the value of that element. - Otherwise, split the segment into two halves and recursively build the left and right subtrees.
- Create a new node whose value is the sum (or other aggregate function) of the values of the left and right children.
Implementation:
def build(arr, left, right):
# Function to build the initial segment tree
if left == right:
# If the current segment is a single element, create a leaf node
return Node(value=arr[left])
# Calculate the mid-point of the current segment
mid = (left + right) // 2
# Recursively build the left and right subtrees
left_child = build(arr, left, mid)
right_child = build(arr, mid + 1, right)
# Create a new node with the sum of values of left and right children
return Node(value=left_child.value + right_child.value, left=left_child, right=right_child)
2. Updating the Segment Tree Persistently
The update
function creates a new version of the segment tree by copying only the necessary parts. It returns a new root node for the updated version, leaving the previous versions intact.
Algorithm:
- If the current segment is a single element (i.e.,
left == right
), create a new node with the updated value. - Otherwise, determine whether the index to be updated lies in the left or right subtree.
- Recursively update the relevant subtree while keeping the other subtree unchanged.
- Create a new node whose value is the sum (or other aggregate function) of the values of the updated left and right children.
Implementation:
def update(prev_node, left, right, idx, new_value):
# Function to perform an update operation on the segment tree persistently
if left == right:
# If the current segment is a single element, create a new node with the updated value
return Node(value=new_value)
# Calculate the mid-point of the current segment
mid = (left + right) // 2
# Determine whether the index to be updated lies in the left or right subtree
if idx <= mid:
# Recursively update the left subtree, keep the right subtree unchanged
left_child = update(prev_node.left, left, mid, idx, new_value)
right_child = prev_node.right
else:
# Recursively update the right subtree, keep the left subtree unchanged
left_child = prev_node.left
right_child = update(prev_node.right, mid + 1, right, idx, new_value)
# Create a new node with the sum of values of the updated left and right children
return Node(value=left_child.value + right_child.value, left=left_child, right=right_child)
3. Querying the Segment Tree
The query
function retrieves information from a segment of the tree. It can perform range queries on any version of the tree.
Algorithm:
- If the query range does not overlap with the current segment, return 0 (or the identity value for the aggregate function).
- If the current segment is completely within the query range, return the value of the current node.
- Otherwise, split the query range and recursively query the left and right subtrees.
- Return the sum (or other aggregate function) of the results of the left and right subtree queries.
Implementation:
def query(node, left, right, query_left, query_right):
# Function to perform a range query on the segment tree
if query_left > right or query_right < left:
# If the query range does not overlap with the current segment, return 0
return 0
if query_left <= left and right <= query_right:
# If the current segment is completely within the query range, return the value of the current node
return node.value
# Calculate the mid-point of the current segment
mid = (left + right) // 2
# Recursively query the left and right subtrees and return the sum of results
return query(node.left, left, mid, query_left, query_right) + query(node.right, mid + 1, right, query_left, query_right)
Persistent Segment Tree in Python
Persistent data structures are a powerful tool in computer science, enabling us to maintain and access multiple versions of a data structure over time. One such structure is the Persistent Segment Tree. Segment trees are versatile data structures that allow efficient querying and updating of array intervals. By making a segment tree persistent, we enhance its capability to maintain historical versions, which is particularly useful in competitive programming and real-time applications where rollback and point-in-time queries are needed. This article explores the concept, implementation in Python.
Contact Us