Segment Trees

What is Segment Tree?

Segment tree is a binary tree where each node represents an interval. The root node represents the whole array and the leaf nodes represent the single element of the array.

Segment tree is a data structure which is used for solving range queries in logarithmic time. It is used for storage of Interval or Segment of elements.

Interval

Interval is a range of elements between the start and end index.Intervals are dynamic as they change during operations. For example, if we have an array of 10 elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Then the interval between the 3rd and 7th index is [3, 4, 5, 6, 7].

Segment

The Segment is little different from the interval. Means, it is refered to a specific range that represented by the node of the segment tree. The segment is static as it does not change during operations it is fixed.

Let's understand the segment with an example.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] // entire array
[1, 2, 3, 4, 5] // segment 1
[6, 7, 8, 9, 10] // segment 2

Here, the entire array is divided into two segments. The first segment is [1, 2, 3, 4, 5] and the second segment is [6, 7, 8, 9, 10].

Usage of Segment Tree with Example

Segment tree is a data structure that is build for solving the range query problems.

For example, you have an array of 10 elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Now you have to find the minimum value between the 3rd and 7th index.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
3rd index = 3
4th index = 4
5th index = 5
6th index = 6
7th index = 7
Minimum = 3

So, the minimum will be 3 between the 3rd and 7th index.

If we solve this problem using the general brute force approch time complexity will be O(n) where n is the total elements of the array. This is not better way to do this problem because if we have a large dataset then it will take more time to find the minimum value.

So, to solve this problem efficiently we can use the segment tree data structure. In this tutorial let's understand how we can solve this problem using the segment tree.

Note : You should be familiar with the recursion and tree data structure before learning the segment tree.

Representation of Segment Tree

Here, we will represent the segment tree using the array. The segment tree is a binary tree where each node represents an interval. The root node represents the whole array and the leaf nodes represent the single element of the array.

In the above image, the segment tree is formed for finding the maximum value in the array [3,2,1,0,4,5] where the segment of the root node is [0,5]. The left child of the root node represents the segment [0,2] and the right child of the root node represents the segment [3,5]. Similary it goes on.

Each node of the segment tree contains the following information:

• Start index of the segment
• End index of the segment
• Maximum value of the segment
• Left child of the segment
• Right child of the segment

How Segment Tree Works?

Segment tree works in the following way:

• Build the segment tree from the given array.
• Perform the range query on the segment tree.
• Update the value of the array and segment tree.

Build the Segment Tree

The sengment tree uses the recursive approach to build the tree. The steps to build the segment tree are:

• Start with the root node that represents the whole array.
• Divide the array into two equal parts and build the left and right child of the root node.
• Continue this process until the leaf node is reached.

Let's understand the steps to build the segment tree with an example.

Example

Now, we will build the segment tree for the sum query of the array [4, 3, 2, 1, 6, 7].

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int nextPowerOf2(int n) {
   int power = 1;
   while (power < n) {
      power *= 2;
   }
   return power;
}

void buildSegmentTree(int *arr, int *segment, int low, int high, int pos) {
   if (low == high) {
      segment[pos] = arr[low];
      return;
   }
   int mid = (low + high) / 2;
   buildSegmentTree(arr, segment, low, mid, 2 * pos + 1);
   buildSegmentTree(arr, segment, mid + 1, high, 2 * pos + 2);
   segment[pos] = segment[2 * pos + 1] + segment[2 * pos + 2];
}

void printSegmentTree(int *segment, int size) {
   for (int i = 0; i < size; i++) {
      printf("%d ", segment[i]);
   }
   printf("\n");
}

int main() {
   int arr[] = {4, 3, 2, 1, 6, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   int segSize = 2 * nextPowerOf2(n) - 1;
   int *segment = (int *)malloc(segSize * sizeof(int));

   for (int i = 0; i < segSize; i++) {
      segment[i] = 0;
   }

   buildSegmentTree(arr, segment, 0, n - 1, 0);
   printSegmentTree(segment, segSize);
   free(segment);
   return 0;
}

23 9 14 4 5 6 7 4 3 2 1 0 0 0

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int nextPowerOf2(int n) {
   int power = 1;
   while (power < n) {
      power *= 2;
   }
   return power;
}

void buildSegmentTree(vector<int> &arr, vector<int> &segment, int low, int high, int pos) {
   if (low == high) {
      segment[pos] = arr[low];
      return;
   }
   int mid = (low + high) / 2;
   buildSegmentTree(arr, segment, low, mid, 2 * pos + 1);
   buildSegmentTree(arr, segment, mid + 1, high, 2 * pos + 2);
   segment[pos] = segment[2 * pos + 1] + segment[2 * pos + 2];
}

void printSegmentTree(vector<int> &segment) {
   for (int i = 0; i < segment.size(); i++) {
      cout << segment[i] << " ";
   }
   cout << endl;
}

int main() {
   vector<int> arr = {4, 3, 2, 1, 6, 7};
   int n = arr.size();
   int segSize = 2 * nextPowerOf2(n) - 1;
   vector<int> segment(segSize, 0);

   buildSegmentTree(arr, segment, 0, n - 1, 0);
   printSegmentTree(segment);
   return 0;
}

23 9 14 4 5 6 7 4 3 2 1 0 0 0

import java.util.Arrays;

public class SegmentTree {
   public static int nextPowerOf2(int n) {
      int power = 1;
      while (power < n) {
         power *= 2;
      }
      return power;
   }

   public static void buildSegmentTree(int[] arr, int[] segment, int low, int high, int pos) {
      if (low == high) {
         segment[pos] = arr[low];
         return;
      }
      int mid = (low + high) / 2;
      buildSegmentTree(arr, segment, low, mid, 2 * pos + 1);
      buildSegmentTree(arr, segment, mid + 1, high, 2 * pos + 2);
      segment[pos] = segment[2 * pos + 1] + segment[2 * pos + 2];
   }

   public static void printSegmentTree(int[] segment) {
      for (int i = 0; i < segment.length; i++) {
         System.out.print(segment[i] + " ");
      }
      System.out.println();
   }

   public static void main(String[] args) {
      int[] arr = {4, 3, 2, 1, 6, 7};
      int n = arr.length;
      int segSize = 2 * nextPowerOf2(n) - 1;
      int[] segment = new int[segSize];

      Arrays.fill(segment, 0);
      buildSegmentTree(arr, segment, 0, n - 1, 0);
      printSegmentTree(segment);
   }
}

23 9 14 4 5 6 7 4 3 2 1 0 0 0

def nextPowerOf2(n):
   power = 1
   while power < n:
      power *= 2
   return power

def buildSegmentTree(arr, segment, low, high, pos):
    if low == high:
        segment[pos] = arr[low]
        return
    mid = (low + high) // 2
    buildSegmentTree(arr, segment, low, mid, 2 * pos + 1)
    buildSegmentTree(arr, segment, mid + 1, high, 2 * pos + 2)
    segment[pos] = segment[2 * pos + 1] + segment[2 * pos + 2]

def printSegmentTree(segment):
    for i in segment:
        print(i, end = " ")
    print()

arr = [4, 3, 2, 1, 6, 7]
n = len(arr)
segSize = 2 * nextPowerOf2(n) - 1
segment = [0] * segSize

buildSegmentTree(arr, segment, 0, n - 1, 0)
printSegmentTree(segment)

23 9 14 4 5 6 7 4 3 2 1 0 0 0

Applications of Segment Tree

Segment tree is used in various applications, such as:

• Range Sum Query
• Range Minimum/Maximum Query
• Range Update Query
• Range Count Query

Conclusion

In this tutorial, we have learned about the segment tree data structure. We have seen how the segment tree is built and how it is used to solve the range query problems. We have also seen the applications of the segment tree in various fields.