Segment Tree

Segment Tree: A Segment Tree is a binary tree used for efficient range queries on an array. It allows us to perform various operations efficiently, such as range sum, range minimum/maximum, and range updates, in logarithmic time complexity.

The basic idea behind a Segment Tree is to divide the array into smaller segments and build a binary tree structure where each node represents a segment of the array. Each node stores information about the segment it represents, such as the sum, minimum/maximum value, or any other relevant information. The leaf nodes of the tree correspond to individual elements of the array.

Construction of Segment Tree: To construct a Segment Tree, we follow a recursive approach called "Build" or "Build Tree." Here are the steps involved:

  1. Define the SegmentTree class with an array and the size of the array as instance variables.
  2. Implement the build_tree method that constructs the segment tree recursively.
  3. In the build_tree method, check if the current node represents a single element (leaf node). If so, assign the value of the array element to the node.
  4. If the current node represents a segment, recursively construct the left and right subtrees and assign the relevant information (e.g., sum, minimum/maximum) to the current node based on the information from its children.

Query Operations on Segment Tree: Once the Segment Tree is constructed, we can perform various query operations efficiently. For example, let's consider the range sum query.

  1. Define the query method that takes the query range (start and end indices) as input.
  2. Check if the current segment node's range is completely outside the query range, in which case return 0 (or an appropriate value depending on the operation).
  3. Check if the current segment node's range is completely inside the query range, in which case return the value of the current node.
  4. If the current segment node's range overlaps with the query range, recursively query the left and right subtrees and combine the results according to the query operation (e.g., sum the results).

Update Operations on Segment Tree: Segment Trees also support efficient update operations. For example, let's consider the update operation to modify a specific element in the array.

  1. Define the update method that takes the index of the element to be updated and the new value as input.
  2. If the current node represents the element to be updated, update its value with the new value.
  3. If the current node represents a segment that contains the element to be updated, recursively update the left and right subtrees.

Example: Let's solve a problem using the Segment Tree concept. One popular problem is "Range Sum Query - Mutable" .

Problem: Given an array nums and multiple queries of range sum, implement the NumArray class to support efficient query and update operations.



class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        self.build_tree(nums)

    def build_tree(self, nums):
        for i in range(self.n, 2 * self.n):
            self.tree[i] = nums[i - self.n]
        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):
        index += self.n
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

    def query(self, left, right):
        left += self.n
        right += self.n
        total_sum = 0
        while left <= right:
            if left % 2 == 1:
                total_sum += self.tree[left]
                left += 1
            if right % 2 == 0:
                total_sum += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
        return total_sum


class NumArray:
    def __init__(self, nums):
        self.segment_tree = SegmentTree(nums)

    def update(self, index, val):
        self.segment_tree.update(index, val)

    def sumRange(self, left, right):
        return self.segment_tree.query(left, right)

Time Complexity Analysis:

  • Construction: O(n)
  • Update Operation: O(log n)
  • Query Operation: O(log n)

Space Complexity: O(n)

In the above example, we have implemented a SegmentTree class that constructs the segment tree and performs update and query operations efficiently. The NumArray class acts as an interface for the user, encapsulating the SegmentTree implementation.

You can create an instance of the NumArray class and use the update method to modify elements in the array and the sumRange method to calculate the sum of a range.

Next Post Previous Post