Range Minimum Query

It’s also a solution to SGU 155. The problem can be viewed here. Every node has two values <k, a>, and we need use them to build a Cartesian tree, in which each node’s k is larger than the left subtree‘s k, but is smaller than the right subtree’s k. Besides, the parent’s a is larger than its child’s a.
The bold word “subtree” is a trap. It means the root’s k is larger than not only its child’s k, but also all other nodes’ k in its left subtree. So an intuitive idea of 1. sorting a first, 2. enumerating nodes, 3. insert node-i as node-(i-1)’s left child if its k is larger than node-(i-1), right otherwise; doesn’t work. To make sure that all nodes in the left subtree have smaller k, we need to sort k at first, and then find the node with smallest a to make it as the root. So here comes the algorithm:

  1. Sort the nodes according to k
  2. Find the node r with the smallest a
  3. Make node r as the root of the tree. The nodes on its left are in its left subtree, and the nodes on its right belong to its left subtree
  4. Iterative the steps 2~4 for the left nodes and right nodes seperatively

We can sort the nodes using Quick Sort in O(nlogn) time. But how could we find the minimum a in the sequence?
Actually it’s a typical problem called Range Minimum/Maximum Query (RMQ in short), which solves the problem of finding the minimal value in a sub-array of an array of comparable objects [1].
There are several versions of RMQ which have different time and space efficiencies. Here I only introduce an online RMQ (ST, Sparse Table) which needs O(nlogn) time for preprocessing, O(1) time for query, and O(nlogn) space for storage.

RMQ

Preprocess

Assume a[i] to be the targeted array, and f[i,j] = min{a[i], a[i+1], …, a[i+2^j-1]}. It’s clear that f[i,0] == a[i]. With initial states f[i,0], we can obtain all f[i,j] using dynamic programming.
For j > 0, f[i,j] equals to the minimum number among even elements. It can be split into two parts,  f[i,j-1] = min{a[i], a[i+1], …, a[i+2^{j-1}-1]}, and  f[i+2^{j-1}, j-1] = min{a[i+2^{j-1}], …, a[i+2^j-1]}. So the state transition equation of this is

f[i,j] = \min\{f[i,j-1], f[i+2^{j-1},j-1]\}

Query

When we call the function RMQ(left, right), it should return the minimum number among those (right-left+1) numbers. These numbers can be covered by two subsets: the first one is {a[left], a[left+1], …, a[p]}, and the second is {a[q], a[q+1], …, a[right]}, where left <= p <= q <= right. A easy solutions to find p and q is to assume k = [log(right-left+1)], and let p = left + 2^k – 1, and q = right – 2^k + 1. In this way, RMQ(left, right) = min{f[left, k], f[right-2^k+1, k]}, which can be returned in constant time.

Reference

[1] http://en.wikipedia.org/wiki/Range_minimum_query

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.