# 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