小於O（n）的稀疏填充數組中的範圍之間的和？

Question

假設有一個巨大的陣列，只有很少的位置被填滿。我需要找到某個位置a和位置b之間的和，即< b。

我能比O（n）做得更好嗎？如果是，如何？

Answer 1

是的，您可以使用二進制索引樹（或段樹）來執行O(logN)查詢。

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ https://en.wikipedia.org/wiki/Fenwick_tree

Answer 2

如果你的稀疏數組作爲一個天真的，本地陣列實現（例如int[999999]）則比O(n/p)時間（其中p是硬件線程你的號碼）手動迭代沒有更快的方法。

如果您的稀疏數組存儲在存儲最佳的格式（例如網頁或鏈表-的-頁的陣列），那麼最快是O(m/p)其中m是頁數和p是多少硬件線程。

UPDATE：

在您的評論你說你想運行比O(n)更快的單線程解決方案。這是不可能的。考慮這個稀疏陣列：

arr = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ] 

計算機不能像一個人的眼睛+大腦一樣「看到」一個陣列。單線程計算機一次只能處理一個字（通常爲32或64位）的數據。所有計算機都知道arr內有一個數組，因此它開始讀取它，它看到0，然後它再次讀取0，依此類推，讀取11 0 s，直到它最終遇到1值。這是O(n)解決方案。

唯一能夠解決這個問題的方法是使用並行化：人眼+大腦可以被視爲具有超過576萬個線程（90度人眼has 576 megapixels）的機器，它可以「看到」整個陣列我的StackOverflow即時發佈（O(1)）。對於一臺計算機做同樣的程序就必須有多個線程（與預編程的數據偏移），它同時讀取數組，然後給你答案：

void Main() { 
    // Setup the threads 
    volatile int total = 0; 
    WaitHandle ev = new WaitHandle(); 
    Int32[] arr; 
    ev.Reset(); 
    for(int i=0; i < 100; i++) { 
     (new Thread(delegate() { 
      int offset = i; 
      ev.WaitOne(); 
      total += arr[offset]; // assume this is a magic thread-safe increment operation 

     })).Start(); 
    } 

    // Load the array 
    Int32[] arr = new Int32[] { /* 100 values */ }; 
    ev.Set(); // unblock all 100 threads instantly 

    // assume there's a magic Thread.Join() wait here 

    Console.WriteLine("Total: {0}.", total); 
} 

這是唯一的出路以數學上合理的方式得到O(1)時間來計算稀疏數組的總和。

...然而，即使這是不可能的，因爲沒有「魔術線程安全加法」操作存在。你可以做的最好的是m - 中間加成操作的級別（其中m是一些Log[X](n)的值），但它仍然非常接近O(1)。