如何使用笛卡爾樹多次從索引i到索引j的數組？

假設我有一個給定的數組A.現在有形式如何使用笛卡爾樹多次從索引i到索引j的數組？

reverse i,j // means reverse the array Ai..j inclusive

和

print i,j

打印陣列Ai..j的多個操作。

例，

A = 6 9 1 10 4 15 9 
reverse 2,3 
A = 6 1 9 10 4 15 9 
reverse 3,6 
A = 6 1 15 4 10 9 9 
print 1,4 

6 1 15 4

我聽說，它可以通過笛卡爾樹來完成。所以我一直在閱讀博客here但我仍然無法理解我們如何使用笛卡爾樹來做到這一點，關鍵和價值應該是什麼以及我們應該如何實現？

來源

2014-10-11 Unbound

'互換（I，J）;''我++''j'重複，直到'I'j' – Haris 2014-10-11 08:12:45

我希望有人誰已經知道笛卡爾樹會能夠回答這個問題，因此沒有必要爲該網站。我提供了該網站，以便人們可以知道我遵循哪種笛卡爾樹的實現方式（並且沒有英文網站實施笛卡爾樹） – Unbound 2014-10-11 08:19:29

在這個問題中，應該使用帶有隱式密鑰的樹（又名笛卡爾樹）（根本沒有密鑰，它只是按照正確的順序合併它們）。節點的值是它表示的數組元素。要實現反向操作，可以爲每個節點保留反向標誌（如果必須反轉則爲true，否則爲false），並且懶惰地推送它（在這裏推入意味着交換節點的左右子節點並翻轉標誌的值它的孩子）。

推送

僞代碼：

void push(Node node) 
    if node.flag 
     swap(node.left, node.right) 
     if node.left != null 
      node.left.flag = not node.left.flag 
     if node.right != null 
      node.right.flag = not node.right.flag

來源

2014-10-11 08:25:52 kraskevich

你能舉個例子嗎？我不明白推動的部分！ – Unbound 2014-10-11 08:31:18

@Unbound我爲推送添加了一個僞代碼。 – kraskevich 2014-10-11 08:36:37

如果我交換節點，wouldnt密鑰更改？我的意思是左邊的子樹應該小於節點，但是當你交換時它變得更大。 – Unbound 2014-10-11 09:53:04

如何使用笛卡爾樹多次從索引i到索引j的數組？

回答

相關問題