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:

- Sort the nodes according to
*k* - Find the node r with the smallest
*a* - 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
- Iterative the steps 2~4 for the left nodes and right nodes seperatively

We can sort the nodes using Quick Sort in *O*(*n*log*n*) 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*(*n*log*n*) time for preprocessing, *O*(1) time for query, and *O*(*n*log*n*) 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

#### 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.