Define a Cartesian tree and its applications.

A Cartesian tree is a binary tree derived from a sequence of numbers, used in various data structure applications.

A Cartesian tree is a specific type of binary tree that is derived from a sequence of numbers. Each node in the tree corresponds to a number in the sequence, and the tree is constructed in such a way that it maintains the properties of both a binary search tree and a heap. This means that an in-order traversal of the tree will give the original sequence, and the parent of any node in the tree is the minimum number in the subsequence to the left or right of that node in the original sequence.

The root of the Cartesian tree is the minimum number in the sequence. To construct the tree, you start with the root and then recursively add the remaining numbers. For each number, you go as far right in the tree as possible until you find a node that is less than the number. This node becomes the parent of the new number, and any right child of this node becomes the left child of the new number.

Cartesian trees have several applications in computer science. They are used in the construction of range minimum query data structures, which are used to quickly find the minimum value in a range of numbers. They are also used in the construction of suffix trees, which are used in string matching algorithms. Additionally, Cartesian trees can be used to solve the nearest smaller values problem, which is to find the nearest number smaller than each number in a sequence.

In summary, a Cartesian tree is a versatile data structure that combines the properties of binary search trees and heaps. It is derived from a sequence of numbers and can be used in a variety of applications, including range minimum queries, string matching, and the nearest smaller values problem.