Segment Tree Implementation in Python
A Segment Tree is a data structure that allows efficient processing of range queries and updates on an array. It is particularly useful for answering queries where the problem can be broken down into smaller overlapping subproblems, such as finding the sum, minimum, or maximum over a range of an array.
Program Structure
The Segment Tree implementation in Python consists of the following components:
1. SegmentTree Class
This class encapsulates the functionality of the Segment Tree. It includes the following methods:
__init__(self, data): Initializes the Segment Tree with a given array of data.build(self, node, start, end): Recursively builds the Segment Tree.update(self, index, value, node, start, end): Updates the value at a given index and reflects the change in the Segment Tree.query(self, L, R, node, start, end): Returns the result of a range query over a specified interval [L, R].
Python Code Implementation
class SegmentTree:
def __init__(self, data):
"""
Initialize the Segment Tree.
:param data: The input array for which the Segment Tree is built.
"""
self.n = len(data)
self.tree = [0] * (2 * self.n)
self.build(data)
def build(self, data):
"""
Build the Segment Tree from the input data.
:param data: The input array.
"""
# Insert leaf nodes in tree
for i in range(self.n):
self.tree[self.n + i] = data[i]
# Build the tree by calculating parents
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
"""
Update the value at a given index in the array.
:param index: The index to update.
:param value: The new value to set.
"""
# Update the leaf node
index += self.n
self.tree[index] = value
# Recalculate the tree
i = index
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, L, R):
"""
Query the sum in the range [L, R].
:param L: The starting index of the range.
:param R: The ending index of the range.
:return: The sum of the elements in the range [L, R].
"""
result = 0
L += self.n
R += self.n
while L <= R:
if L % 2 == 1:
result += self.tree[L]
L += 1
if R % 2 == 0:
result += self.tree[R]
R -= 1
L //= 2
R //= 2
return result
Explanation
The Segment Tree implementation is based on storing the entire tree in a single array, where leaf nodes (the elements of the input array) are stored in the second half, and internal nodes are stored in the first half.
1. SegmentTree Class
The SegmentTree class manages the operations of the Segment Tree.
Initialization
The __init__ method initializes the tree with the given array of data. The size of the tree array is twice the size of the input array to accommodate both leaf and internal nodes.
Build
The build method constructs the tree by inserting the input array’s elements as leaf nodes and then calculating the internal nodes (parent nodes) by summing the values of their children.
Update
The update method changes the value of a specific element in the input array. After updating the leaf node, it recalculates the values of the internal nodes to reflect the change.
Query
The query method returns the sum of elements within a specified range [L, R]. It uses the properties of the segment tree to efficiently combine the results from the necessary segments.
Usage Example
# Example usage of the SegmentTree
# Initialize a Segment Tree with the given array
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)
# Query the sum of elements in the range [1, 3]
print("Sum of elements in range [1, 3]:", seg_tree.query(1, 3))
# Output: Sum of elements in range [1, 3]: 15
# Update the value at index 1 to 10
seg_tree.update(1, 10)
# Query again after the update
print("Sum of elements in range [1, 3] after update:", seg_tree.query(1, 3))
# Output: Sum of elements in range [1, 3] after update: 22
This example demonstrates how to create a Segment Tree, query the sum of a range of elements, update an element, and then query the range again to see the effect of the update.
