Non-Recursive Segment Tree


Segment Tree is a data structure used to efficiently answer range-based queries on an array. The Non-Recursive implementation of the Segment Tree avoids the use of recursion and uses an iterative approach to build and query the tree. Let's go through the explanation, implementation, and solve a LeetCode problem using this concept.

Segment Tree:

Segment Tree is a binary tree that represents intervals or segments of an array. Each node in the tree represents a segment, and the leaf nodes represent individual elements of the array. The parent node of any segment represents the union or combination of its child segments.

Non-Recursive Approach:

In the non-recursive approach, we use an iterative process to build and query the segment tree. The steps involved are as follows:

  1. Building the Segment Tree:

    • Start with an empty array tree of size 2 * n, where n is the length of the input array.
    • Fill the leaf nodes of the tree with the values from the input array.
    • Iterate from n - 1 to 1 (in reverse order) and compute the values for the parent nodes by combining the values of its children.
    • The value at each parent node is determined based on the specific operation required for the problem at hand (e.g., sum, min, max, etc.).

  2. Querying the Segment Tree:

    • To answer a range-based query, start from the root of the tree and traverse down based on the given range.
    • At each level, determine if the current segment is completely outside the given range, completely inside the given range, or partially overlapping with the given range.
    • Depending on the case, adjust the range and traverse to the appropriate child segment.
    • Combine the values of the segments encountered during the traversal to compute the result.

Example:

Let's consider an example to understand the non-recursive segment tree implementation. Suppose we have an input array [1, 3, 5, 7, 9], and we want to perform range sum queries on this array.


# Non-Recursive Segment Tree Implementation

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

    def build(self, arr):
        n = len(arr)
        for i in range(n):
            self.tree[n + i] = arr[i]
        for i in range(n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

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


# Example Usage
arr = [1, 3, 5, 7, 9]
segment_tree = SegmentTree(arr)
print(segment_tree.query(1, 3))  # Output: 15

In this example, we define a SegmentTree class with methods for building the tree and performing range sum queries.

We initialize the tree list with double the length of the input array arr. We then fill the leaf nodes of the tree with the values from arr. Next, we iterate in reverse order from n - 1 to 1 and compute the parent node values by combining the values of its children using the sum operation.

For the query method, we start with the left and right indices of the range to query. We adjust the indices to correspond to the leaf nodes of the tree. We then traverse the tree while updating the indices and accumulating the sum based on the range and the values encountered during traversal.

Finally, we create an instance of the SegmentTree class with the input array [1, 3, 5, 7, 9] and perform a range sum query from index 1 to index 3. The output is 15, which is the sum of the elements in the range [3, 5, 7].

Time and Space Complexity:

The time complexity of building the segment tree is O(n), where n is the length of the input array. The time complexity of the range sum query is O(log n), as we traverse the tree in a binary search-like manner.

The space complexity is O(n) as we create a segment tree of size 2 * n to store the tree nodes.

Let's solve the problem "Range Sum Query - Mutable" using the concept of a non-recursive segment tree.

Problem: Range Sum Query - Mutable

You are given an integer array nums and an array queries, where queries[i] = [left_i, right_i] represents a query for the sum of the elements in the subarray nums[left_i, right_i] (inclusive).

You need to implement the NumArray class:

  • NumArray(nums) Initializes the object with the integer array nums.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • int sumRange(int left, int right) Returns the sum of the elements of the nums array in the range [left, right] (inclusive).

Solution:

 


# Non-Recursive Segment Tree Implementation

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

    def build(self, nums):
        n = len(nums)
        for i in range(n):
            self.tree[n + i] = nums[i]
        for i in range(n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, val):
        n = len(self.tree) // 2
        index += n
        self.tree[index] = val
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

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


# Example Usage
nums = [1, 3, 5, 7, 9]
queries = [[1, 3], [2, 4]]
num_array = NumArray(nums)
output = []
for query in queries:
    output.append(num_array.sumRange(query[0], query[1]))
print(output)  # Output: [15, 21]

In this example, we define the NumArray class that uses a non-recursive segment tree to solve the problem.

The __init__ method initializes the segment tree by calling the build method, which constructs the tree based on the input array nums.

The update method updates the value of an element at a specific index. We adjust the index to correspond to the leaf nodes of the tree and update the value. Then, we propagate the changes upward in the tree to maintain the correct sums.

The sumRange method computes the sum of the elements in the given range. We adjust the left and right indices to correspond to the leaf nodes of the tree. We traverse the tree while accumulating the sum based on the range and the values encountered during traversal.

Finally, we create an instance of the NumArray class with the input array [1, 3, 5, 7, 9]. We perform two range sum queries, and the output is [15, 21], which represents the sum of the elements in the ranges [3, 5, 7] and [5, 7, 9].

The time and space complexity of this solution is the same as the non-recursive segment tree implementation explained earlier.

Next Post Previous Post