先前 我寫了兩種 "看起來" O(nlgn) 的做法。

動態記憶體: http://codepad.org/7UwGMBfg

陣列: http://codepad.org/nBjxQ0p4

寫完 動態記憶體 後,自信滿滿的以為 O(nlgn) 會過,沒想到竟然 TLE!

我想可能是 動態記憶體 太慢,所以就改成 陣列 的寫法,還是 TLE!

我起初很訝異,這題確實是可以 O(n)<笛卡爾樹,可是我還不會XD>,後來才發現我的複雜度根本估錯了。

如果他給的序列 剛好是 遞增或遞減 的話,每次更新變成了 O(n),總複雜度 O(n^2),就輕鬆 TLE了。

或許 平衡樹 可以解決這個問題(?)。

所以說 以上 是篇廢文,不過 複雜度 真的要會估(死~)。

-------------------------------------------------

現在開始才是真正的 O(n) 題解。

首先要來介紹一個很特殊的資料結構,笛卡爾樹。

這裡只講要用到的部分,其實他還有其他比較重要的應用。

笛卡爾樹是指把該序列 最小(大) 的值當作 樹根,其 右邊 與 左邊 分別是一顆 笛卡爾樹。

 

以上就是一顆簡單的 笛卡爾樹 啦(畫好爛= =)。

至於要怎麼使用呢?

我們存一個 a[i] 表示 i 第幾個插入。

舉例: 3 1 2 4 5

a[1] = 2, a[2] = 3, a[3] = 1, a[4] = 4, a[5] = 5。

我們用 新的序列 做一顆 笛卡爾樹。

轉換回去

神奇的事情發生了!為什麼呢?

因為

在BSTree上x就是根

他要找b[1]~b[x-1]最小得當他左子節點

找b[x+1]~b[n]最小得當他右子節點

就這樣遞迴下去

他剛好符合迪卡爾樹

圖論真奇妙 --引用自 fenzhang

所以 我們得到了一個結論,靜態的 (1~n) BST 我們可以在 O(n) 建立出來。

 我的code

http://codepad.org/6aj99CUQ
 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()