笛卡兒樹

笛卡兒樹是一種特殊的堆，它的重要套用之一是實現rmq問題向LCA問題的轉化。
笛卡兒樹根據一個數列構造，其根結點是長為n的數列A中的最小值A的下標i，左右
孩子分別是由數列A[1...i-1]和A[i+1...n]構造的笛卡兒樹。下面的內容里，我們說笛卡
兒樹某結點的值，指的是其存儲的下標在原數組裡對應的值。
由於笛卡兒樹的這一特性，不難發現求原數列A的某一段最小值，相當於求這一段的
左右兩端在笛卡兒樹上所對應結點的最近公共祖先。
這裡有一個定理：
數組A的Cartesian樹記為C(A)，則RMQ(A,i,j)=LCA(C(A),i,j).
證明略。
現在急待解決的問題是笛卡兒樹的建立方法。笛卡兒樹不一定是完全二叉樹，所以與
堆的操作有些不同。由於笛卡兒樹的特性，對其進行中序遍歷一定會得到原數列，也
就是說，可以把笛卡兒樹看作是將原數列中的最小值“提升”到最高處，再將左右兩部
分的最小值分別“提升”到次高處…，最終形成一棵二叉樹。所以我們由A[1]開始逐個
將數列里的數加入笛卡兒樹內，新加入的結點一定在樹的最右路徑的最右端(沒有右
孩子)。當加入A時我們在已有的笛卡兒樹上找到最右路徑上找到大於A最小值，將
它的父結點作為新結點的父結點，它則作為新結點的左孩子。若根結點大於A則整個
樹作為新結點的左孩子，若最右路徑上沒有大於A的結點，則A加入最右路徑的最
右下端。
由於每個結點最多進入和退出最右路徑各一次，因此均攤時間複雜度為θ(n)。