因此,我讀了this RMQ(範圍最小查詢)的TopCoder教程,我得到了一個很大的問題。範圍最小查詢<O(n), O(1)>方法(從樹到受限制的RMQ)
在那裏他介紹了 approach的部分,有什麼我能理解到現在爲止是這樣的:
(整個逼近實際使用的方法在Sparse Table (ST) Algorithm介紹,Reduction from LCA to RMQ和from RMQ to LCA)
給定一個數組A [N],我們需要將它轉換爲笛卡爾樹,從而使RMQ問題成爲LCA(最低共同祖先)問題。稍後,我們可以獲得數組A的簡化版本,並使其成爲受限制的RMQ問題。
所以它基本上是兩個轉換。所以第一個RMQ到LCA部分很簡單。通過使用堆棧,我們可以在O(n)時間內進行變換,產生一個數組T [N],其中T [i]是元素i的父元素。樹完成。
但這是我無法理解的。 O(n)方法需要一個數組,其中|A[i] - A[i-1]| = 1
和該數組在本教程的Reduction from LCA to RMQ部分中介紹。這涉及到這棵樹的歐拉遊。但是,如何通過轉換的最終結果實現這一目標?我的方法不是線性的,所以在這種方法中應該被認爲是不好的,那麼線性方法是什麼?
UPDATE:
歐拉遊需要知道每個節點的孩子,就像一個DFS(在深度:這讓我困惑
Here's the array A[]:
n : 0 1 2 3 4 5 6 7 8 9
A[n]: 2 4 3 1 6 7 8 9 1 7
Here's the array T[]:
n : 0 1 2 3 4 5 6 7 8 9
T[n]: 3 2 0 * 8 4 5 6 3 8 // * denotes -1, which is the root of the tree
//Above is from RMQ to LCA, it's from LCA to RMQ part that confuses me, more below.
樹的圖片中的點First Search),而T [n]只有每個元素的根,而不是子。
我不確定我是否理解你的意思,「我的最終結果是如何實現這一轉變」。你能詳細說明什麼是特別令你困惑嗎? – templatetypedef 2013-02-08 17:14:03
@templatetypedef好的,我會將它添加到問題中。 – 2013-02-08 17:18:17
@templatetypedef已添加。 – 2013-02-08 17:22:46