如何提高此算法的時間複雜度？

Question

• n列表大小
• v[n]列表設置爲0
• update(k, a)操作這臺v[k] += a
• query(a, b)操作返回的v[a] + v[a+1] + ... + v[a+b]總和所有值，a<b

這些操作給算法時間複雜度爲O(n * cost of one operation)：

--------------------------- 
| update | query | total | 
--------------------------- 
| O(1) | O(n) | O(n) | 
--------------------------- 

是否有任何版本的update和query操作將提高總時間複雜度？

比如我試圖緩存0和n之間的每一筆在update操作，但我得到一個更慢的算法：

--------------------------- 
| update | query | total | 
--------------------------- 
| O(n^2) | O(1) | O(n^2) | 
--------------------------- 

有什麼建議？

最糟糕的情況是我感興趣的。

我已經知道兩個版本：每個版本都有一個操作O(1)和其他O(n)或更高版本。

Answer 1

感謝@Niklas B的評論之一。我一直在關注分段樹的研究。

線段樹的表示

• 葉節點是輸入數組
• 的元件各自內部節點表示節點
下的葉節點的一些合併
• 合併是葉總和
• 使用樹的陣列表示來表示針對索引爲i的每個節點的分段樹
• ，左邊的孩子是在指數2*i+1，右孩子在2*i+2和家長在floor((i-1)/2)

段樹建立從給定數組

• 開始與段arr[0, .., n-1]
• 鴻溝（如果它還沒有變成長度爲1的段）
• 在兩半上調用相同的過程，並且對於每個這樣的段我們將總和存儲在相應的節點中
• 構造的分段樹的所有級別將完全填充，除了最後一級。
• 樹將是滿二叉樹，因爲我們總是在各個層面
• 分爲兩半段，因爲建造樹總是與n葉滿二叉樹，會有n-1內部節點
• 總數節點將是2*n – 1。

時間複雜度

• 樹構建有O(n)
• 總共有2n-1節點，每個節點的值在樹結構只計算一次
• 查詢有O(Logn)
• 查詢總和，我們在每個級別最多處理四個節點，級別數量爲O（Logn）。
• 更新也已經O(Logn)

• 更新葉子值，我們處理在各個層面和級別的頭號節點O(Logn)

  ------------------------------- 
  | update | query | total | 
  ------------------------------- 
  | O(Logn) | O(Logn) | O(Logn) | 
  ------------------------------- 
  

參考文獻：

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

http://en.wikipedia.org/wiki/Segment_tree

Answer 2

正如Niklas指出的，這個問題或多或少是Fenwick trees的設計目的（您的查詢可以作爲兩個前綴和的差異來回答）。我在寫這個答案時指出，有可能以不同的方式折算運營成本。

首先，您的低價查詢算法可以將其更新時間提高到O（n）：提前計算前綴總和並使用上述差異技巧。此外，我們可以提取的主要思想，並將其應用到支持業務

update(k, a, b): for i in a..b, do s[i] += k 
query(i): return s[i], 

其中s現在擁有前綴總和，而不是實際值的任何數據結構。

現在，典型的Fenwick /段樹每個內部節點有d = 2個子節點（是二進制的）。沒有任何東西阻止我們選擇其他的d值。 update或query必須訪問節點及其祖先，另一個必須訪問包含輸入時間間隔的段。前一種訪問模式需要花費時間O（log n/log d）。後者模式需要時間O（d（log n/log d））。在這個框架中，你提出的算法本質上是d = n。通過採用d的其他值，我們可以說明查詢/更新操作的精確組合以及可能有利於平坦樹結構的架構細節。