Segment Tree (Build and Range Query Operations)

We use the Segment Tree to efficiently answer multiple range queries on an array. It also help us to modify the array by replacing an element or an entire range of elements in logarithmic time. In this blog, we will focus on two critical operations: building the segment tree from a given array and performing a range minimum operation on a segment tree.

Let's start with this problem: We have an array with some integers. Now we receive multiple range queries [l, r], and the answer to each query is the minimum value from the array between the positions l and r.

Example

Suppose the input array is arr[] = [3, 6, 2, 1, 5, 10, 2, 11, 4, 8]. The following are the queries and their corresponding answers.

Range: [4, 8], Output: 2.

Explanation: We need to return the minimum from the array between indices l = 4 and r = 8. So, if we look at the subarray arr[4:8] = [5, 10, 2, 11, 4], the minimum in this range is 2. So the answer to this query is 2.

Range: [1, 3], Output: 1.

Explanation: We return the minimum value from the subarray arr[1:3] = [6, 2, 1], which is 1.

Brute force solution for Range Minimum Query problem

We iterate from index l to r in the array for each query, finding the minimum value within this range. So, one query takes O(r - l) time or O(n) time in the worst case. If there are q queries, this method will take O(q * n) time in the worst case. One insight is clear: as the number of queries increases, code will take a significant time to process all queries. So, goal is to design a data structure that can answer each query efficiently.

How does Segment Tree works?

A segment tree is a binary tree in which each node stores information about a specific range, and the nature of that information depends on the problem. In our case, each node will store the minimum value within an interval. However, segment trees can also be used to store various types of information like range maximum, range sum, range XOR, etc.

To build a segment tree, we use the array representation of a binary tree. If we follow 0-based indexing, for any node at index i, its children will be found at indices 2i + 1 and 2i + 2. Similarly, with 1-based indexing, the children of a node at index i will be present at indices 2i and 2i + 1. In this blog, we will follow 0-based indexing.

Suppose we are given an array arr[] with a size of n and the segment tree st[].

The root of the segment tree represents the entire range of the array from 0 to n - 1, i.e., arr[0: n-1].
Leaf nodes of st[] represent individual elements from arr[i].
Internal nodes represent an interval arr[i: j], where 0 <= i < j < n.

We then break down this interval into two half intervals. The children of the root node represent the intervals arr[0, n/2] and arr[n/2 + 1, n - 1]. Each interval is further divided into two halves, and the two children of each node represent these halves. Since the segment tree halves in each step, the height of the segment tree is O(log n) and the tree has n leaves, corresponding to the n indices in the array.

For example, explore the following image of the segment tree for the given array. The red text represents the current node's range, the blue text denotes the node's indexes, and the black text shows the minimum value from the array in this range.

Segment tree visualization

How to Build a Segment Tree for Range Minimum Queries?

Divide and Conquer Idea to Build Segment Tree

As we know, both children of a node share the node’s range equally. So, we use a divide and conquer strategy to build the segment tree. During the divide step, we proceed top-down and recursively split the range into two halves until only one element remains. This single-element range is the base case.

The segment tree is formed during the conquer-and-combine step, which proceeds in a bottom-up fashion, starting from the leaf nodes and moving toward the root. In other words, it updates the nodes along the path from a leaf to the root, using data from the child nodes to construct a parent node at each step. This recursive process ultimately reaches the root, which represents the entire array. Note: The combine step may vary for different types of queries, such as range-maximum and range-sum queries.

Divide and Conquer Steps to Build Segment Tree

We define a function buildSegTree(int st[], int arr[], int nodeIndex, int leftRange, int rightRange) that takes these values as input parameters:

st[]: Segment tree array.
arr[]: Input array.
nodeIndex: Index of the current node in the segment tree.
leftRange: Left limit of the current segment.
rightRange: Right limit of the current segment.

Initially, nodeIndex = 0(root node), leftRange = 0, and rightRange = n - 1.

Divide Step: By calculating the mid-index, we divide the array into two halves: leftRange to mid and mid + 1 to rightRange, where mid = leftRange + (rightRange - leftRange)/2.

Conquer Step: We recursively call the same function with modified input parameters to build the segment tree for the left and right half of the array i.e. buildSegTree(st, arr, 2 * nodeIndex + 1, leftRange, mid) and buildSegTree(st, arr, 2 * nodeIndex + 2, mid + 1, rightRange).

Combine Step: This is the most crucial step. We use the data of the child nodes to decide what information the parent node stores. In our case, we need to find the range minimum. So we take the minimum of the values stored in the child nodes and keep them in the parent node i.e. st[nodeIndex] = min (st[2 * nodeIndex + 1], st[2 * nodeIndex + 2]). Note: If we need to find the range sum, we will take the sum of the values stored in the child nodes and store it in the parent node.

Base Case: This is the trivial case when leftRange == rightRange, i.e. this represents a single element from the array which is the situation of a leaf node. The segment tree will store this element i.e. if(leftRange == rightRange), st[nodeIndex] = arr[leftRange].

Size of the array used in Segment Tree Construction

As discussed above, we represent the segment tree as an array, similar to the heap. The difference here is that the heap is a complete binary tree structure, while the segment tree is a full binary tree structure. The idea is simple: We always divide segments into two halves at every level in a segment tree.

Here are the properties of a full binary tree:

Every node has 0 or 2 children.
In a full binary tree with n leaves, there will be n-1 internal nodes. So the total nodes will be 2*n – 1.
Unlike a complete binary tree, the last level in a full binary tree may have gaps between nodes. So there will be some wastage of space in the simple array representation of a full binary tree. We can think to optimize this wastage, but code for segment tree operations becomes more complex.

If the size of the input array n is a power of 2, then the size of the segment tree is 2n - 1, where the number of leaf nodes is n and the number of internal nodes is n - 1. Now, if we increase the input array size by 1, a new level gets added to the tree. So if n is not a power of 2, we need to go to the next power of 2. In other words, when the array size n is not a power of 2, approximately 2k - 1 nodes are required for the segment tree, where k is the smallest power of 2 greater than n.

For example, take this array and the corresponding segment tree for finding the minimum in a range, where the size of the array varies from 1 to 5. Initially, arr = [1], st = [1], size of the tree = 1.

arr = [1, 2], st = [1, 1, 2]

The size of tree = 3 (2n -1, where n = 2).

Now n = 3, arr = [1, 2, 3], st =[1, 1, 3, 1, 2, null, null]

Here n is not a power of 2.
The smallest power of 2 greater than n = k = 4.
So the size of the tree = 2 * k - 1 = 2 * 4 - 1 = 7.
If we observe, the height of the tree increases by 1.

arr = [1, 2, 3, 4], st = [1, 1, 3, 1, 2, 3, 4]

The size of tree = 7 (2n -1, where n = 4).

arr = [1, 2, 3, 4, 5], st =[1, 1, 4, 1, 3, 4, 5, 1, 2, null, null, null, null, null, null]

Here n is not a power of 2.
The smallest power of 2 greater than n = k = 8.
So the size of the tree = 2 * k - 1 = 2 * 8 - 1 = 15.
The height of the tree again increases by 1 at this point.

Pseudocode for Building Segment Tree

buildSegTree(st, arr, nodeIndex, leftRange, rightRange)
    if leftRange equals rightRange
        // This node represents one array element.
        st[nodeIndex] = arr[leftRange]
        return

    mid = leftRange + (rightRange - leftRange) / 2
    // Build the left and right child subtrees.
    buildSegTree(st, arr, 2 * nodeIndex + 1, leftRange, mid)
    buildSegTree(st, arr, 2 * nodeIndex + 2, mid + 1, rightRange)
    // Store the minimum of the two child ranges.
    st[nodeIndex] = min(st[2 * nodeIndex + 1], st[2 * nodeIndex + 2])

buildSegmentTree(arr, n)
    if n equals 0
        return an empty array
    // Allocate enough space for the segment tree array
    st = array of size 4 * n
    buildSegTree(st, arr, 0, 0, n - 1)
    return st

Time Complexity of Building a Segment Tree

We recursively solve the problem of size n by solving the two smaller sub-problems of size n/2 and using the solutions of these two smaller problems to answer the parent node.

The time complexity of the divide part is O(1).
The time complexity of the conquer part is 2*T(n/2).
The time complexity of the combine part is O(1).
Thus, overall time complexity T(n) = 2 * T(n/2) + O(1).

We can solve this recurrence using both the recursion tree and the master method. To better understand analysis, you can refer to this blog: Analysis of recursion. If we observe closely, this recurrence relation is similar to the recurrence of the divide and conquer solution of finding max and min in an array. So the time complexity is O(n). In other words, we can build a segment tree in linear time.

Space Complexity of Building a Segment Tree

Space complexity = Space used for st[] array + Space used by recursion call stack.

As discussed above, If the size of the input array n is a power of 2, then the size of the segment tree is 2n -1. If n is not a power of 2, then the segment tree size is 2k - 1, where k is the smallest power of 2 greater than n. So overall, the size of the st[] array will be O(n). The critical idea to explore: A common implementation allocates 4n slots to safely store the tree. 4n is not the number of actual tree nodes, it is extra capacity to accommodate gaps in the array representation.
For the recursion call stack, space complexity is O(log n) as the stack frame size depends on the recursion tree's max depth, which is equal to O(log n).

So overall space complexity = O(n) + O(log n) = O(n).

How does Query work in Segment Tree?

Algorithm idea of Range Minimum Query

In this operation, we query on a range and return the answer to the problem (minimum of the range in our case). We start from the root of the segment tree. At each node, we check for three conditions:

If the range represented by the node is completely outside the given range: In this case, we do not move ahead and return.
If the range represented by a node is entirely inside the given range: In this case, we return the value stored at this node, a minimum of the range defined by the node.
If the range represented by a node is partially inside and partially outside the given range: we query both children then return the smaller of their results.

Pseudocode of Range Minimum Query

st[]: Segment tree array.
nodeIndex: Index of the current node in the segment tree. This will be 0 Initially.
leftRange: Left limit of the current node.
rightRange: Right limit of the current node.
queryLeft: left limit of the given query.
queryRight: right limit of the given query.

rangeMinQuery(st, nodeIndex, leftRange, rightRange, queryLeft, queryRight)
    // The node's interval is completely outside the query range.
    if queryRight < leftRange or rightRange < queryLeft
        return +infinity

    // The node's interval is completely inside the query range.
    if queryLeft <= leftRange and rightRange <= queryRight
        return st[nodeIndex]

    // The intervals partially overlap, so query both children.
    mid = leftRange + (rightRange - leftRange) / 2

    leftMin = rangeMinQuery(
        st, 2 * nodeIndex + 1, leftRange, mid, queryLeft, queryRight
    )
    rightMin = rangeMinQuery(
        st, 2 * nodeIndex + 2, mid + 1, rightRange, queryLeft, queryRight
    )

    return minimum of leftMin and rightMin

For example, let's consider the array:

Index: 0 1 2 3 4 5.
Value: 2 5 1 4 9 3.

Suppose we query the minimum from index 1 to index 4 i.e. range minimum of [1, 4]. Here, the root represents [0, 5], which only partially overlaps the query, so the algorithm checks both children:

Left child [0, 2]: It partially overlaps the query, so it checks [0, 1] and [2, 2].
- [0, 1] partially overlaps. Its child [0, 0] is outside the query, so it returns +∞. [1, 1] is fully inside, so it returns 5. Their minimum is 5.
- [2, 2] is fully inside the query, so it returns 1.
- The minimum for [0, 2] is min(5, 1) = 1.
Right child [3, 5]: It partially overlaps the query, so it checks [3, 4] and [5, 5].
- [3, 4] is fully inside the query, so it returns its stored minimum 4.
- [5, 5] is outside the query, so it returns +∞.
- The result from the right side is min(4, +∞) = 4.

Finally, the algorithm combines both sides: min(1, 4) = 1. So the minimum in the range [1, 4] is 1.

Time Complexity of Range Minimum Query

To query a range minimum, we claim that we process at most two nodes at every level. We will attempt to prove this through a contradiction. For example, consider the following tree. Suppose that three nodes are explored at a certain level in the given segment tree.

The range covered by these nodes is from the leftmost colored node to the rightmost colored node. But in this case, the range of the middle node is entirely covered. This node will immediately return the value and not be explored. So we proved that we expand at most two nodes at each level, and since there are logn levels, the number of explored nodes is 2logn = O(logn). Time complexity of the query operation is O(logn).

Conclusion

In this blog, we studied how to solve multiple queries on an array in logarithmic time. We looked at the build and query operations of the segment tree. In the next blog, we will study the update operation of the segment tree.

Enjoy learning, Enjoy coding, Enjoy algorithms!

Segment Tree Data Structure (Build and Range Query Operations)