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],
- The root of the Tree contains the minimum value of the whole array, or the minimum value in the range [0, n – 1].