數據結構<O（n）的元素0的總和查詢多達n

Question

作爲一個例子，假設你有在一個列表中的以下數字在此給定的順序：

list = [4, 10, 3, 5, 1] 

所以列表[0] == 4和列表[4] == 1.

現在想象一下，您需要一個總和查詢，它會告訴您以前所有值的總和，直到給定的位置。

list.sum(0) == 4 
list.sum(1) == 14 
list.sum(2) == 17 
list.sum(3) == 22 
list.sum(4) == 23 

此外，我想下面的操作，同時仍保持和查詢完整：

list.swap(0, 1) // swap the two positions 
list == [10, 4, 3, 5, 1] 
list.slideBefore(0, 3) // slides 1st position value to before the 2nd position 
list == [4, 3, 10, 5, 1] 
list.slideAfter(2, 3) // slide 1st position value to after 2nd position 
list == [4, 3, 5, 10, 1] 
list.replace(3, 9) // replace value at 1st param with literal value 2nd param 
list == [4, 3, 5, 9, 1] 
list.append(17) // adds value to end 
list == [4, 3, 5, 9, 1, 17] 

這可能是由陣列平凡處理。但總和查詢總是O（n）。我希望能夠找到一個數據結構，它將總和查詢保持在O（1）或O（lg n），同時還將上述操作保持在O（1）或O（lg n）。

我相信我可能可以操縱fast array數據結構來完成我想要的功能，但是我沒有完全解決它。

我看到的另一個數據結構是Fenwick樹，但是我不清楚它會工作。

任何建議，想法，技巧或提示？

Answer 1

考慮一個簡單的數組，您可以將總和存儲到此元素而不是元素中。 在這種方式中，

int sum(int n){ 
    return array[n]; // O(1) ! 
}; 

int elem(int n){ 
    if (n) 
     return array[n] - array[n-1]; 
    return array[0]; 
}; 

這將有O（1）次，所有的操作，不同replace，這將需要爲O（n）。

您也可以考慮一個二進制樹，它只保存葉子中的值，並將其子節點的總和保存在每個節點中。

Answer 2

您要使用的數據結構將取決於您的訪問模式。如果查詢非常頻繁且修改操作不頻繁，那麼如果設置了「髒」標誌，則可以維護一個「髒」標誌並重新計算查詢的總和。

然後，您可以通過設置一個「髒指數」（其中包含已更改的最低項目的指數）來優化該指標。在查詢時，您必須重新計算該項目的總和以及之後的所有項目。或者，也許只有達到您需要的項目，您才能更新「髒指數」。

如果查詢頻繁且修改不頻繁，或者該模式在進行大量修改之後進行大量查詢，那麼這種懶惰評估可能非常有效。

'swap'和'append`可以在O（1）時間內完成，並且如果它們還不是髒的，它們就不會「髒」這些總和。 '替換'當然會導致髒指數設置在該指數（當然，它並不是已經處於較低指數）。

slidebefore和slideafter本質上是O（N）如果您的數據結構是一個數組，因爲您必須移動數組中的數據。在你的榜樣，您有：

list == [10, 4, 3, 5, 1] 
list.slideBefore(0, 3) // slides 1st position value to before the 2nd position 
list == [4, 3, 10, 5, 1] 

所以項目1和2中的數組必須向左移動一個位置進行重新定位的空間項目0。如果您有slideBefore(0, 1000)，則陣列中的1,000個項目必須向上移動一個位置。如果這些操作頻繁且列表很大，則可能需要不同的底層表示。

另一種可能性是「列表清單」實現。想象一下20個項目的列表，這些項目分爲4個子列表，每個列表包含5個項目。每個子列表都維護項目的計數和項目的總和。子列表中的每個節點都維護列表中所有項目之前的所有項目的運行總和。當你更新一個物品時，你只需要更新該物品的子清單的總和。同樣，如果你使用懶惰評估，如果有人被查詢，你只能重新計算以下子列表的總和。

要處理插入和刪除操作，允許子列表在分割之前增大到某個最大值。說你的「理想」是每個子列表五項。但是你可以讓它增長到10個，然後再分成兩個子列表。對於刪除，您可以允許子列表變爲0，或者如果子列表中的項目少於3個，可以將其與前一個或下一個子列表結合使用。

子列表的理想大小取決於您希望列表中的項目總數，以及您希望遇到的操作組合。本質上爲O（N）的操作（如移除和滑動）將有利於較小的子列表，但隨着重新計算變得更加昂貴，因爲您有更多的子列表。

這並沒有真正改變算法的運行時複雜度（即O（n/5）仍然被認爲是O（N）），但它的確會改變運行時間很多。對於中等大小的列表，它可能是一個真正的勝利。