Segment Tree

Segment tree is a data structure that is used to solve a certain problem, called RMQ (Range Minimum Query).

What is RMQ?

Given the following problem to solve: We have an array arr[0..n-1]. We should be able to do:

• Find the minimum element from index l to r where 0 <= l <= r <= n-1
• Change value of a specified element of the array to a new value x ie. arr[i] = x where 0 <= i <= n-1.

Naive solution

One way to do this is to iterate from l to r indices of array arr[]. This would give the time complexity of O(n), where n is the number of elements in array arr.
This seems a feasible solution. But what if we have n queries. Then this solution won’t be able to work for a larger n. As the time complexity would be O(n²).

Segment Tree

Segment tree is a balanced binary tree of height log(n). Each node in the Segment Tree represents an interval. Consider an array A of size N and a corresponding Segment Tree:

• Leaf nodes are the elements of the input array arr.
• Internal nodes represent minimum/maximum of all leaves under it. For instance internal node: 1 ([0-5]) represent minimum value for all elements in arr[0..5]. Similarly, node 1 ([0-2]) represent minimum value for all elements in arr[0..2].

Given a problem of RMQ, where objective is to find the minimum element of the array in the given range [x, y]

Preprocessing time to construct the segment tree is O(n). And time for range minimum query is O(logn). RMQ works same as finding a node in a balanced binary tree.

To find:

• Children node for node i, left child is at index 2*i + 1 & right child is at index 2*i + 2.
• Parent node for a child node i is at (i-1)/2.

Get min query (RMQ)

Querying constructed segment tree to find the minimum value in range [x, y].

Constructing Segment tree

// sb = segmentBegin
// se = segmentEnd
// This method build our segment tree ie. the array seg
int construct (int arr[], int sb, int se, int si) {

  // Base case (only 1 element)
  if (sb == se) {
    seg[si] = arr[sb];
  } else {
    int mid = (sb+se)/2; // Dividing given range in two equal halves
    
    seg[si] = min((construct(arr, sb, mid, 2*si + 1)),
                  (construct(arr, mid+1, se, 2*si + 2)));
  }

  return seg[si];
}

Height of constructed segment tree is log_2(n) . Size of memory allocated for segment tree is 2*2^{log_2(n)} - 1 (max number of nodes in a binary tree of height ‘h’ is 2^h+1 – 1) ie. 2n -1, where n is size of array. This implies space complexity of segment tree is O(n).

Get min query

int getMin(int sb, int se, int x, int y, int i) {
 
// Base case: Out of bound range
 if (sb > y || se < x) {
   return INT_MAX;
 } else if (sb >= x && se <= y) {
   // Node in permissible range, 
   // send the value of internal node (i) 
   return seg[i]; 
 } else {
   int mid = (sb+se)/2;

   // Checking children nodes [(2*i+1), (2*i+2)]
   return min((getMin(sb, mid, x, y, 2*i + 1)),
              (getMin(mid+1, se, x, y, 2*i + 2)));
 }
}

Output

arr[] = {1, 3, 2, 7, 9, 11}

Minimum element in the range:
x = 1, y = 5: 2
x = 0, y = 3: 1
x = 3, y = 5: 7
x = 0, y = 4: 1

Here’s a working example: Segment Tree (Get Min Query)

Get max query (RMQ)

Similarly, we could create segment tree for Get Max Query, by replacing min operation with max operation on nodes of segment tree. Querying constructed segment tree to find the maximum value in range [x, y].

Constructing Segment tree

int construct (int arr[], int sb, int se, int si) {
  
  // Base case (only 1 element)
  if (sb == se) {
    seg[si] = arr[sb];
  } else {
    int mid = (sb+se)/2;  
    seg[si] = max((construct(arr, sb, mid, 2*si + 1)), 
                  (construct(arr, mid+1, se, 2*si + 2)));
  }

  return seg[si];
}

Get max query

int getMax(int sb, int se, int x, int y, int i) {
 
 // Base case: Out of bound range
 if (sb > y || se < x) {
   return INT_MIN;
 } else if (sb >= x && se <= y) {
   return seg[i]; 
 } else {
   int mid = (sb+se)/2;
   return max((getMax(sb, mid, x, y, 2*i + 1)),  
              (getMax(mid+1, se, x, y, 2*i + 2)));
 }

}

Output

arr[] = {1, 3, 2, 7, 9, 11}

Maximum element in the range:
x = 1, y = 5: 11
x = 0, y = 3: 7
x = 3, y = 5: 11
x = 0, y = 4: 9

Here’s a working example: Segment Tree (Get Max Query)

Get sum query (RMQ)

The code structure is very similar to the problem of finding the minimum or maximum element in the given range. The only difference is the value we’ll save in segment tree. Querying constructed segment tree to find the sum of values in the range [x, y].

Constructing Segment tree

int construct (int arr[], int sb, int se, int si) {

    if (sb == se) {
      seg[si] = arr[sb];
    } else {
      int mid = (sb+se)/2;
      seg[si] = ((construct(arr, sb, mid, 2*si + 1)) +
                 (construct(arr, mid+1, se, 2*si + 2)));
    }

    return seg[si];
}

Get Sum Query

int getSum(int sb, int se, int x, int y, int i) {
    if (sb > y || se < x) {
       return 0;
    } else if (sb >= x && se <= y) {
       return seg[i];
    } else {
       int mid = (sb+se)/2;
       return (getSum(sb, mid, x, y, 2*i + 1) + 
               getSum(mid+1, se, x, y, 2*i + 2));
    }
}

Output

arr[] = {1, 3, 2, 7, 9, 11}

Sum in the range:
x = 0, y = 2: 6
x = 3, y = 4: 16
x = 2, y = 5: 29
x = 3, y = 5: 27
x = 0, y = 5: 33

Here’s a working example: Segment Tree (Get Sum Query)

In the next post, we’ll learn about update query along with RMQ.