Range Minimum Query – Segment Tree (Java)

Tags: , ,

Given an array, there is a popular problem to search the minimum value in a range [a, b]. This is called Range Minimum Query. This post describes a method to solve the range minimum query problem using Segment Tree.

The basic idea of a Segment tree is as follows:

Given an array A with size n:  the index of the array looks like this [0, 1, 2, ...., n-1], 

  1. The root of the Tree contains the minimum value of the whole array, or the minimum value in the range [0, n - 1]. 
  2. Then the left child of the root contains the minimum value of the left half part of the array: the minimum value in the range [0, mid],
  3. The Right child of the root contains the minimum value of the right half part of the array: the minimum value in the range [mid + 1, n-1],

where mid = (0 + n -1 ) / 2.

In other worlds:

Apparently, we can build the tree recursively. The pseudo code is as following:

How can we use the tree to do range minimum query:

We start from the root of the tree: range(root = 0, start = 0, end = n - 1, qstart, qend)

  1. if [start, end] is in the range of the query [qstart, qend], we immediately know that Tree[root] is the answer. 
  2. If the query range [qstart, qend] is in the range of [start, end], we can search the left tree and right tree, then return the minimum value
  3. If there is no overlapping,  we return Integer.Max value. 

The pseudo code looks like this:

The following is the code with test:

Reference:

Introduction to Algorithms