範圍最小查詢<O(n), O(1)>方法（從樹到受限制的RMQ）

因此，我讀了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：

The Cartesian Tree from the data

歐拉遊需要知道每個節點的孩子，就像一個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]只有每個元素的根，而不是子。

來源

2013-02-08 Shane Hsu

我不確定我是否理解你的意思，「我的最終結果是如何實現這一轉變」。你能詳細說明什麼是特別令你困惑嗎？ – templatetypedef 2013-02-08 17:14:03

@templatetypedef好的，我會將它添加到問題中。 – 2013-02-08 17:18:17

@templatetypedef已添加。 – 2013-02-08 17:22:46

這是我目前什麼迷惑你的理解：

爲了減少RMQ到LCA，您需要將數組轉換成一棵樹，然後做樹的歐拉。
爲了進行歐拉遊覽，您需要存儲樹，以便每個節點指向其子節點。
從RMQ到LCA列出的減少量，每個節點都指向它的父代，而不是其子代。

如果是這樣，您的擔心是完全正確的，但有一個簡單的方法來解決這個問題。具體來說，一旦你擁有了所有父指針的數組，你可以將它轉換爲樹，每個節點在O（n）時間點指向它的子節點。這個想法如下：

創建一個n個節點的數組。每個節點都有一個值字段，一個左邊的孩子和一個右邊的孩子。
最初，將第n個節點設置爲空左子節點，空右子節點以及數組中第n個元素的值。跨越第t陣列（其中，T [n]是n的父索引）
迭代並執行以下操作：
- 如果T [N] = *，則第n個條目是根。您可以將其存儲起來供以後使用。
- 否則，如果T [n] < n，那麼你知道節點n必須是它的父節點的右子節點，它存儲在位置T [n]。因此，將第[n]個節點的右側子節點設置爲第n個節點。
- 否則，如果T [n]> n，那麼您知道節點n必須是其父節點的左子節點，它存儲在位置T [n]。因此，將第[n]個節點的左側子節點設置爲第n個節點。

這將運行在時間爲O（n），因爲每個節點被處理一次。

完成此操作後，您已明確構建了需要的樹結構並且有一個指向根的指針。從那裏開始，應該合理簡單地繼續算法的其餘部分。

希望這會有所幫助！

來源

2013-02-08 18:01:18 templatetypedef

謝謝！它確實有幫助，很多！感謝您花費這麼多時間評論和回答！ – 2013-02-08 18:05:44

範圍最小查詢<O(n), O(1)>方法（從樹到受限制的RMQ）

回答

相關問題