# 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:

**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.).

- Start with an empty array
**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.