樹簡介

笛卡爾樹是平衡二叉樹的一種，他和我們之前學習的AVL樹一樣通過旋轉來調整蓖康，使平衡樹達到平衡態(tài)蓉坎。不過，不同的是：笛卡爾樹除了用于決定節(jié)點向左/右分布的key外唠粥，還有個value疏魏，用來決定節(jié)點的層級先后。

笛卡爾樹的分布存在以下特點：

• key:分布遵循BST的規(guī)律晤愧，即左子樹key<根key<右子樹key
• value:分布遵循堆的規(guī)律大莫，即父value < 子value/子value < 父value
  • 父value < 子value: 最小堆
  • 子value < 父value：最大堆

樹操作算法概述

笛卡爾樹我們只介紹建樹的過程。忽略樹的修改操作官份。

建樹

笛卡爾樹的key遵循二叉搜索樹的特點只厘。value遵循堆的特點。所以我們先把數據按照key從小到大進行排序舅巷⌒赴迹【以此為例，如果你硬要從大到小也是一樣的道理】

接下來我們只需要從第一個節(jié)點開始串下去就行了悄谐，后面的肯定比前面的大介评，所以在前面節(jié)點的右子樹或者父節(jié)點，而是右子樹還是父節(jié)點，通過value判定们陆。

一個二叉樹大概長下面這樣【網上盜的圖寒瓦，不是搜索樹，大概看個結構就行】：

1.png

既然不是當右兒子就是當爸爸坪仇，我們在構建過程中直接把根節(jié)點到最右子樹存下來杂腰，方便為新來的節(jié)點找到進入的位置。

存儲的東西如下：

2.png

每新來一個節(jié)點椅文，我們拿著value一個一個比較喂很，因為父value要比子value大。而且有一個特點皆刺，新插入一個點后少辣，原來他右下位置的點就變成他的左子樹了，右鏈砍掉了一部分羡蛾。所以有兩種思路：

1. 每次從根往右遍歷
   • 和當前的節(jié)點比較漓帅，當前節(jié)點比插入值大就繼續(xù)向后遍歷，直到遇到一個比他小的痴怨，然后插到他的前面忙干，他后面的節(jié)點做插入點的左子樹
2. 每次從右下角遍歷
   • 和當前的節(jié)點比較，當前節(jié)點比插入值小就過浪藻，繼續(xù)向前遍歷捐迫，找到對應位置，插進去

兩種方法其實都是一個思路：遍歷爱葵，直到找到合適位置施戴，然后插入。

在網上找到的很多源碼都提到了O(n)時間復雜度的笛卡爾樹構造方法钧惧，說是借助棧暇韧，他們一般用的是我介紹的第二種思路：和棧頂比較勾习，不行就扔掉浓瞪，插進去后入站，然后新的右鏈就又在棧中了巧婶。

如果你思路清晰了乾颁，完全可以不借助棧，直接從根節(jié)點右子樹右子樹的遍歷就行艺栈，都不用維護棧了英岭。

源碼

直接放項目的地址了，我是用的java寫的增刪操作湿右，沒有用C诅妹。還有就是沒有專門為這個建git，源碼在com.gateway.learn.tree下面。github地址：https://github.com/LiPengcheng1995/gateway-parent.git

樹應用場景

官方話：

笛卡爾樹是一種特定的二叉樹數據結構吭狡，可由數列構造尖殃，在范圍最值查詢、范圍top k查詢（range top k queries）等問題上有廣泛應用划煮。它具有堆的有序性送丰，中序遍歷可以輸出原數列。

（用數組下標當key）

自己的話：

笛卡爾樹我認為其實最重要的并不是key弛秋，而是value：

key存在的意義是為了讓數列中相鄰的節(jié)點繼續(xù)相鄰器躏，比較形象一點的形容就是只看key的話可以把key當作數列的下標，然后從中間把這個數列拎起來蟹略，就形成了樹結構登失。

value存在的意義你可以看作數組中存的值，你給整個數列做了一個排序后的存儲科乎，只不過你把排序結果放在了樹的上下結構中壁畸，節(jié)點下標沒變。

問題一

這個樣一個問題：求[a,b]范圍中的最大值茅茂，你只需要找到a,b節(jié)點的LCA(Lowest Common Ancestor)捏萍，即最近公共祖先。

思路分析

1. 構建笛卡爾樹
2. 依靠二叉排序樹的特點快速定位LCA
3. 返回查到的LCA的value值

本文算法時間復雜度分析

1. 構建笛卡爾樹 O(n)空闲。（因為以下標為key令杈，不需要重新排序了，用棧來輔助理解就是每個元素只會有一次進棧）
2. 依靠二叉排序樹特點快速定位LCA O(log2(n))【平衡二叉樹樹深碴倾，雖然笛卡爾樹的平衡不一定有VAL樹那么平逗噩，但是大概還是平的】
   • this.key < a-->右邊走
   • this.key > b --->左邊走
   • 遇到的第一個a<this.key<b，this.value就是結果
3. return this.value

所以時間復雜度為O(n)跌榔。當然异雁，如果多次查詢只需要一次建樹，這就很爽了僧须，時間復雜度為O(log2(n))纲刀。

傳統(tǒng)算法時間復雜度分析

順序遍歷一遍，記一下最大就行担平，時間復雜度為O(n)示绊。

比較

本文算法優(yōu)點：

1. 多次查詢只需一次建樹
2. 查詢效率穩(wěn)定，（已經構建笛卡爾樹后暂论，區(qū)間范圍越大查詢效果往往越快）

本文算法缺點：

1. 存儲樹結構有一一定開銷
2. 不穩(wěn)定面褐，存在極度變態(tài)數列情況下整棵樹被拉成一個鏈的可能

問題二

這樣一個問題：已知一個無序數組，我給你其中一個下標取胎，你要告訴我這個下標對應的值是多大范圍內的最大/小值

思路分析

1. 構建笛卡爾樹展哭，如果求最大值，就按照最大堆構建【后面都按照最大來講，最小也是同理】
2. 笛卡爾樹看下標是樹匪傍，看值是堆坝咐，找到對應的點，它下面的值都比它小析恢，找到他的子樹中的最左邊點墨坚、最右邊點即可

本文算法時間復雜度

1. 構建樹，需要
2. 找節(jié)點對應子樹的最大最小映挂，即是兩個范圍點【找最左/最右子樹即可】泽篮，復雜度為樹深度，都是

綜上柑船，復雜度為

問題三

這個樣一個問題：求[a,b]范圍中的第n大的值帽撑。

思路分析

1. 構建笛卡爾樹
2. 依靠二叉排序樹的特點快速定位LCA
3. 看LCA下面一層夠不夠數
   • 夠就找到第n-1大的
   • 不夠就從再下一層找，設本層有m個點
     • 這一層夠就找第n-m-1大的
     • 不夠再去下一層鞍时。亏拉。。逆巍。及塘。。

時間復雜度分析

1. 構建笛卡爾樹 O(n)
2. 找LCA O(log2(n))
3. 找第n大的锐极，由于樹每靠上一層笙僚，本曾的節(jié)點數以指數倍減少，所以我們可以近似看成常數（可以灵再。肋层。。吧翎迁，總之需要比較的很少了）栋猖、

所以時間復雜度為O(n)。當然汪榔，如果多次查詢只需要一次建樹蒲拉，這就很爽了，時間復雜度為O(log2(n))揍异。

傳統(tǒng)算法時間復雜度分析

得對這一段區(qū)間進行排序全陨，時間復雜度為O(nlog2(n))

比較

如果區(qū)間隨便給爆班，這么查的話衷掷，還是本文的算法好。缺點和上一個問題一樣就不提了柿菩。

還有一個明顯的缺點戚嗅，就是如果對同一個區(qū)間你經常查top k 。直接用傳統(tǒng)方法排個序反而比較快∨嘲看自己需要什么了替久。

問題四

給出n個非負的整數，表示直方圖中每個條的高度躏尉，且每個條的寬度均為1蚯根，找出這些條覆蓋的最大面積的矩形。

3.png

思路分析

1. 構建笛卡爾樹胀糜，（最小堆）
2. 后序遍歷颅拦，將每個節(jié)點的所有子節(jié)點數目存在這個節(jié)點里，并求出子節(jié)點數目和此節(jié)點value的乘積教藻。找到乘積最大的那個結果

幫助理解：

• 子節(jié)點數目 = 這個節(jié)點的value是多少個節(jié)點中最小的 = 涂色長方形的底邊寬是多少
• 此節(jié)點value = 這n個節(jié)點的高度最小值 = 涂色長方形的高

注意：

• 因為是按照下標為key進行排的距帅，原來相鄰的長條現在還是相鄰，所以才能這么等效

時間復雜度分析

1. 構建笛卡爾樹 O(n)

2. 后續(xù)遍歷括堤、計算碌秸、存儲，因為只遍歷一遍悄窃，所以時間復雜度是 O(n)

思路分析（基礎）

上面的雖然說著通順讥电，但是正常人的思路并不是這樣的。你可以這樣想轧抗，底和高都變化允趟，我們需要先找兩者的關聯，先構建出一個合適的計算公式：

從底入手

我們需要遍歷底邊的所有匹配段情況鸦致，并算出區(qū)域內的最低點【數組一端區(qū)間內的最小值】潮剪，這樣需要構建笛卡爾樹，因為匹配的不確定性分唾，我們需要枚舉底邊的(1+2+...+n)種情況抗碰，復雜度是。當然绽乔，如果你硬要把每次確定最小值的操作算到求高的操作中去的話弧蝇，就是 。

從高入手

前面一個思路折砸，我們解決的最大的問題是把范圍確定后的定高問題解決了看疗，但是確定底邊取值范圍開銷太大了，達到了級別睦授。

遇到了這么亂的思路两芳，一般有兩個可能：

1. 問題就是挺亂的。就像我們某些不合理的需求一樣去枷，屎一樣的需求怖辆，再怎么捋代碼也是亂七八糟
2. 我們抽象的不對

我們抽象出了底邊x和高y,然后求xy的乘積最大值是复。我們求x時即使使用普通的排序方法，不用笛卡爾樹也還有竖螃，但是找底邊時我們直接就沖著去了淑廊，這就給人不協調的感覺了。

所以我們進行更近一步的抽象特咆，設從x到y(tǒng)季惩，取這范圍內的長方形，設高的最小值為z腻格，這樣x,y,z的判斷就都是了蜀备，當然，直接一下荒叶，復雜度直接就是了碾阁。

我們需要找到三個變量之間的關系。

如果我們確定一個x,后面y每個取值對應的高度都有可能變化些楣，變化根據數組來變脂凶，沒有規(guī)律，而沒有規(guī)律就意味著遍歷愁茁，意味著低效蚕钦。

如果確定y，是一樣的道理鹅很。

如果我們確定z嘶居，那就無所謂了，x和y往開的撐就行了促煮。撐的越開邮屁，面積越大。

所以我們從z入手菠齿，算出每個z的值都能對應最大多大的(y-x)佑吝，也就是z值都是多大區(qū)間內的最小值。此處回到問題二绳匀。只需要遍歷即可芋忿，所以時間復雜度是：

1. 構建笛卡爾樹
2. 一一求出每個高度對應的底邊最大值【對應的最大最小的范圍】(n個，每個疾棵，也就是
3. n個方案戈钢，在一一計算時順手存下最小的值以及計算方案即可，無需多余的時間復雜度

所以時間復雜度降低到了是尔。

文獻參考

1. https://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html
2. https://blog.csdn.net/pipisorry/article/details/39033269
3. https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91
4. https://agatelee.cn/2016/07/%E6%A0%91%E7%B1%BB%E9%97%AE%E9%A2%98%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91/
5. https://zh.wikipedia.org/wiki/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91