Welcome to our comprehensive guide on the Segment Tree! This data structure is a powerful tool for solving problems efficiently, particularly when it comes to range queries and updates. Let's dive right in!
A Segment Tree is a data structure used to represent a set of numbers, allowing us to perform range operations in logarithmic time, which is much faster than linear time.
š” Pro Tip: If you're not familiar with Big O notation, don't worry! We'll cover that later in the lesson.
Segment Trees are particularly useful when we need to perform queries on a range of elements in an efficient manner. For example, finding the sum of all numbers in a range, finding the maximum or minimum value in a range, or even updating a range of elements.
A Segment Tree is built by dividing the original array into smaller subarrays and creating a new tree-like structure. Each node in the tree represents a subarray of the original array, and the values at each node are the sum (or maximum, minimum, etc.) of the subarray it represents.
To build a Segment Tree, we'll follow these steps:
2 * n (where n is the size of the original array).Now that we've built our Segment Tree, we can perform range queries and updates!
To perform a range query, we'll find the appropriate nodes in the Segment Tree that represent the given range and compute the result based on the stored values at those nodes.
To update a range, we'll recursively find the appropriate nodes in the Segment Tree and adjust their values based on the update we want to make.
Let's look at a practical example to better understand how Segment Trees work.
def build_segment_tree(arr):
# Base case: if the array is empty, return an empty list
if len(arr) == 0:
return []
# Calculate the size of the Segment Tree array
size = 2 * len(arr)
# Create the Segment Tree array and initialize all values to 0
seg_tree = [0] * size
build_helper(arr, seg_tree, 0, len(arr), 1)
return seg_tree
def build_helper(arr, seg_tree, start, end, tree_index):
# If the current segment is the entire array, store the sum of the array
if start == end:
seg_tree[tree_index] = arr[start]
return
# Calculate the midpoint of the current segment
mid = (start + end) // 2
# Recursively build the left and right subtrees
build_helper(arr, seg_tree, start, mid, 2 * tree_index)
build_helper(arr, seg_tree, mid + 1, end, 2 * tree_index + 1)
# Store the sum of the current segment by combining the sums of the subtrees
seg_tree[tree_index] = seg_tree[2 * tree_index] + seg_tree[2 * tree_index + 1]
What is the time complexity of building a Segment Tree from an array of size `n`?
## Queries and Updates
We'll now implement functions to perform range queries and updates using the Segment Tree.
```python
def query(seg_tree, start, end, query_start, query_end, tree_index, sum=0):
# If the current segment is outside the query range, return 0
if query_end < start or end < query_start:
return 0
# If the entire current segment is within the query range, return the sum of the segment
if query_start <= start and end <= query_end:
return seg_tree[tree_index]
# Calculate the midpoint of the current segment
mid = (start + end) // 2
# Recursively query the left and right subtrees and sum their results
left_sum = query(seg_tree, start, mid, query_start, min(mid, query_end), 2 * tree_index, sum)
right_sum = query(seg_tree, mid + 1, end, max(mid + 1, query_start), query_end, 2 * tree_index + 1, sum)
# Return the combined sum of the subtrees
return left_sum + right_sum
def update(seg_tree, start, end, index, new_val, tree_index, sum=0):
# If the index is outside the range of the current segment, return
if index < start or end < index:
return
# If the index is within the current segment, update its value and recursively update the subtrees
if start == end:
seg_tree[tree_index] = new_val
return
# Calculate the midpoint of the current segment
mid = (start + end) // 2
# Recursively update the left and right subtrees
update(seg_tree, start, mid, index, new_val, 2 * tree_index, sum + (end - start + 1) * (seg_tree[tree_index] - new_val))
update(seg_tree, mid + 1, end, index, new_val, 2 * tree_index + 1, sum - (mid - start + 1) * (seg_tree[tree_index] - new_val))
# Update the value at the current node
seg_tree[tree_index] = new_val
What is the time complexity of performing a range query or update using a Segment Tree?
And there you have it! With this detailed guide, you're now well-equipped to understand and implement Segment Trees. Happy coding! š