範圍查詢半羣運算符（union）

Question

我正在尋找實現一個算法，給定一個整數數組和一個範圍（區間）列表，在該數組中返回每個區間中不同元素的數量。也就是說，給定數組A和範圍[i，j]返回集合{A [i]，A [i + 1]，...，A [j]}的大小。

很顯然，天真的方法（從i到j迭代並忽略重複計數）太慢了。範圍總和似乎不適用，因爲AUB-B並不總是等於B.

我查了維基百科的範圍查詢，它暗示姚（82年）顯示了一個算法，運算符（聯合似乎是）具有線性預處理時間和空間以及幾乎不變的查詢時間。不幸的是，這篇文章無法自由獲得。

編輯：看來這個確切的問題，請http://www.spoj.com/problems/DQUERY/

Answer 1

有它使用O（N日誌N）的時間和空間的預處理和O（日誌N）的每個查詢時間，而簡單的算法。首先，創建一個用於回答範圍總和查詢的持久分段樹（最初，它應該包含所有位置的零）。然後迭代給定數組的所有元素並存儲每個數字的最新位置。在每次迭代時創建持久段樹的新版本，將1置於每個元素的最新位置（在每次迭代中，只有一個元素的位置可以更新，因此只有一個位置的值在段樹中發生變化，因此可以在O（log N））。爲了回答一個查詢（l，r）你只需要在（l，r）段上找到在遍歷初始數組的r元素時創建的樹的版本的和。 希望這個算法足夠快。 Upd。我的解釋中存在一個小錯誤：在每一步中，分段樹中最多有兩個位置的值可能會發生變化（因爲如果更新的話，需要將0置於數字的前一個最新位置）。但是，它不會改變複雜性。

Answer 2

您可以通過執行二次時預計算回答您的任何疑問的固定時間：

For every i from 0 to n-1 
    S <- new empty set backed by hashtable; 
    C <- 0; 
    For every j from i to n-1 
     If A[j] does not belong to S, increment C and add A[j] to S. 
     Stock C as the answer for the query associated to interval i..j. 

這個算法需要二次的時間，因爲每個區間，我們執行操作的有限數量的，每一個都需要一定的時間（注意集合S由一個散列表支持），並且有一個二次數的間隔。

如果您沒有關於查詢的更多信息（查詢總數，間隔分佈），則基本上無法做得更好，因爲間隔總數已經是二次方。接收的形式A [i..j]，預先計算的查詢（在O(n)時間）對於所有的間隔A[i..k]答案後，k>=i：

可以通過n線性上即時計算折衷二次預計算。這將保證分期償還的複雜性將保持二次方，並且您不會被迫在開始時執行完整的二次預計算。

請注意，由於您完全掃描了每個區間，所以顯而易見的算法（在語句中稱爲明顯的算法）是立方體。

Answer 3

下面是另一種可能與分段樹有密切關係的方法。將數組元素看作完整二叉樹的葉子。如果數組中有2^n個元素，則該整棵樹有n個級別。樹存儲的每個內部節點上存在葉子下方的點的聯合。數組中的每個數字需要在每個級別出現一次（如果有重複，則數量較少）。所以空間成本是log n的一個因素。

考慮長度K的範圍A..B您可以通過形成用樹葉和節點相關聯的集合的並集摸出點的工會在此範圍內，選擇節點儘可能高的樹，儘可能長因爲這些節點下面的子樹完全包含在範圍內。如果沿着範圍很大的子樹挑選子樹，您會發現子樹的大小先增加然後減小，並且所需子樹的數量只隨着範圍大小的對數增長 - 開始時如果你只能取一個大小爲2^k的子樹，它將在可以被2 ^（k + 1）整除的邊界上結束，並且你將有機會得到一個大小至少爲2 ^（k + 1）的子樹作爲下一個如果你的範圍足夠大的話，一步。

所以回答查詢所需半羣操作次數爲O（log n）的 - 但請注意，半羣操作可能是昂貴的，因爲你可能會形成兩個大集合的並集。