RMQ(Range Maximum/Minimum Query) 和 LCA(Least Common Ancestor) 问题是关联度十分高的两类问题。既可以把LCA问题转化为RMQ问题，也可以把RMQ问题转换 为LCA问题。本文主要探讨如何通过笛卡尔树(Cartesian Tree)来建立起这两类问题之间的联系。

笛卡尔树的特点

笛卡尔树的特点如下：

  • 每一个节点的值都是该节点极其子树的最小值。

笛卡尔树的构造

有笛卡尔树的特点，不难想到其构造算法如下：

  1. 从左到右遍历数组；
  2. 把第一个值作为最初的根节点；
  3. 随后每一个值都从根节点出发，一直向右走，知道找到第一个比该值小的节点；
  4. 把这个值放在找到的节点处，原来该位置的节点作为这个值的左子节点。

示例：

数组：

[10, 25, 22, 34, 7, 19, 9, 12]

加入第一个值:

            1(10)

加入第二个值:

            1(10)
                \
                 \
                2(25)

加入第三个值:

            1(10)
                \
                 \
                3(22)
                /
               /
            2(25)

加入第四个值:

            1(10)
                \
                 \
                3(22)
                /  \
               /    \
            2(25)    4(34)

加入第五个值:

                5(7)
                /
               /
            1(10)
                \
                 \
                3(22)
                /  \
               /    \
            2(25)   4(34)

加入第六个值:

                5(7)
                / \
               /   \
            1(10)   6(19)
                \
                 \
                3(22)
                /  \
               /    \
            2(25)   4(34)

加入第七个值:

                5(7)
               /   \
              /     \
          1(10)     7(9)
             \     /
              \   /
            3(22) 6(19)
            /   \
           /     \
        2(25)    4(34)

加入第八个值:

                5(7)
               /   \
              /     \
          1(10)     7(9)
             \     /  \
              \   /    \
            3(22) 6(19) 8(12)
            /   \
           /     \
        2(25)    4(34)