用於修整數組中較大值的數據結構？

Question

我需要爲以下目的有一個數據結構。假設我有一個數組a。最初所有元素都設置爲零。無論何時我要更新位置p上正數值new_value中的一個元素，如果位置pold_value上的原始值不爲零並且大於new_value，那麼我需要更新從位置p開始的所有非零元素一直到數組的末尾。這裏的更新意味着將該位置的舊值與new_value之間的較小值重新設置。

例如，該陣列是： [2, 0, 3, 0, 2, 1, 5, 0, 4, 0, 7]

鑑於4對於具有一箇舊值3位置2（從0開始）的新值，我需要更新所述陣列爲：

[2, 0, 3, 0, 2, 1, 4, 0, 4, 0, 4]

如果在位置2的新值是1，則所得到的數組是：

[2, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]

有沒有已知的數據結構可以有效地做到這一點？我需要很多這樣的更新操作。

謝謝您的建議。

Answer 1

我相信Cartesian tree可能會幫助你解決你的問題。與維基百科中描述的唯一區別在於，我建議您在每個點頭中構建最大堆而不是最小堆（即，將屬性更改爲每個節點的值不小於它的子節點）。 您需要轉到當前節點的右側子節點，並沿樹形結構向下，更改所有值大於新值的元素。你可以證明這種方式你不會再檢查3 * K元素，其中K是需要改變的元素的實際數量。另一件好事是，通過執行描述每個頂點堆屬性的操作仍將保留，因爲您更改了全部的值大於新值。

希望此回答有幫助。

Answer 2

我相信你可以通過使用splay樹的修改，使每個元素訪問或值更改的分期O（log n）時間得到這個工作。這種方法背後的想法是雙重的。首先，我們不是將數組存儲爲數組，而是將它作爲一對保存原始值的數組和一個splay樹進行存儲，其中每個節點的鍵都是數組中的索引。例如，假定七個要素的數組，設置可能是這樣的：

Array: 3 1 4 2 5 9 3 
Tree:    3 
       / \ 
       1. 5 
      /\./\ 
      0. 2 4. 6 

注意的是，這棵樹上的索引到數組，而不是數組元素本身。如果我們想在特定的索引處查找一個值，我們只需對索引進行splay tree查找，然後返回給定位置處的數組元素，這需要分攤O（log n）時間。

您希望支持更改所有未來值的操作我將稱之爲「天花板」操作，因爲它會在當前所有值之後設置一個上限。考慮這一點的一種方式是數組中的每個元素都有一個與之相關的天花板（最初是無限的），而元素的真實值則是其真實值和天花板的最小值。訣竅是，通過使用splay樹，我們可以通過分攤的O（log n）時間來調整所有值的上限。爲此，我們通過讓每個節點存儲代表從該元素向前施加的上限的值c來擴充splay樹，然後根據需要對c進行適當的更改。

例如，假設我們想從某個元素向前施加一個上限。假設這個元素已經在樹的根部。在這種情況下，我們只需將它的c值設置爲O（1）時間的新上限。從這一點開始，每當我們查看某個元素之後或之後的某個值時，我們就可以記下從樹根到元素的樹狀結構。更一般地說，當我們進行查找時，每次我們遵循一個正確的子鏈接時，我們都會注意到該節點的c值。一旦我們觸及到元素的問題，我們就知道元素的上限，因爲我們可以從我們遵循的正確子節點的根目錄獲取路徑上節點的最小上限。因此，爲了查找結構中的元素，我們執行標準的splay樹查找，跟蹤我們去的c值，然後輸出原始數組值和c值的最小值。

但是爲了做到這一點，我們的方法必須考慮到splay樹的旋轉這一事實。換句話說，我們必須展示如何在旋轉過程中傳播c值。假設我們想要做這樣一個旋轉：

A.   B 
    /.  ->. \ 
    B.    A 

在這種情況下，我們不改變任何C值，因爲任何價值擡頭在A後仍然會通過的節點。然而，如果我們進行相反的旋轉並將A拉到B以上，那麼我們將A的c值設置爲B的c值和A的c值的最小值，因爲如果我們在執行旋轉後下降到A的左子樹中，則需要因子B的上限考慮在內。這意味着我們每輪執行O（1）次工作，並且由於每次展開所執行的已分攤循環次數爲O（log n），因此我們會對每次查找進行分攤O（log n）工作。

要完成圖片，要更新任意天花板，我們展示其上限要更改爲根的節點，然後設置其c值。總之，我們有O（log n）查找O（log n）更改時間（攤銷）。

這個想法是基於來自Sleator和Tarjan的原創論文「Self-Adjusting Binary Search Trees」的鏈接/剪切樹的討論，該文章還介紹了splay樹。

希望這會有所幫助！

Answer 3

我最初的想法有點類似於templatetypedef's answer（+1，順便說一句），但是使用了一個簡單的靜態二叉樹而不是一個splay樹。就像在該答案中那樣，'邏輯'數組L由實際數組A表示，其包含原始值和強制上限值的二叉樹T。 （在這種情況下，最大值樹的形狀是靜態的，因此我們不需要跟蹤樹中元素的索引：對應於節點的索引就是它的有序遍歷索引）只要樹的高度最小，樹就可以是任何形狀;也就是說，如果L包含n元素和2^(k-1) <= n < 2^k，那麼該樹應具有高度k。我會建議一個佈局，我們將元素2^(k-1) - 1放在樹的根部，使其左子樹perfect樹包含L[0 .. 2^(k-1) - 2]，並遞歸地爲L[2^(k-1) .. n - 1]（即它可能爲空）定義其右子樹。例如，一個12元素樹將有條目如下：

   7 
     /-----/ \-----\ 
     3    11 
    /-/ \-\   /-/ 
    1  5  9 
/\ /\ /\ 
0 2 4 6 8 10 

（請注意，這些數字是不是樹的條目 - 他們只是表明什麼位置陣列中的樹的條目對應。）此說明還給出了查找樹中對應於n中的條目i的條目的算法：如果i < 2^(k-1) - 1則在完美左子樹中找到i th條目，如果i = 2^(k-1) - 1那麼它是根，否則找到i - (2^(k-1) - 1) th條目在右子樹中遞歸地輸出n - (2^(k-1) - 1)。

我們將所有樹條目初始化爲無窮大。當我們要處以c天花板進入i後來，我們發現在樹中i個條目，如下所示：

• 如果我們要尋找的節點x是i個節點或我們需要下降到左邊的子樹，我們將存儲在節點x中的值更新爲最小值c和當前值x。
• 如果我們需要陷入的x的右子樹並保存在x當前值最多c，我們並不需要更新樹 - 它已經執行的，所以我們可以停下來。
• 如果x是第i節點，我們可以停止。

這都是爲了施加上限。請注意，A本身從不更新。

如果我們要查找的L的i個值，然後我們初始化一個局部變量c到無窮遠，並找到在樹中i個條目根據這些規則：

• 如果節點x我們正在查看的是第i th節點，或者我們需要下降到右邊的子樹，然後將c設置爲其當前值的最小值以及存儲在x處的值。
• 如果x是第i節點，我們可以停止。

現在我們返回最小值A[i]和c。

這兩個操作都是O(log n)（每個操作的實際時間，不是攤銷）。爲了實現，請注意，您可以使用數組來保存二叉樹。