如何確定一個範圍內有多少元素在另一個給定範圍內？

Question

我需要一點點的幫助，試圖找出事情：

鑑於無序號（小於超過15.000）的序列 - 一個 - 我必須回答Q查詢（Q < = 100000）

多少號碼範圍[I，J]從A是大於x大於y與所有大（或相等），但更小的：形式I，J，X，Y其翻譯爲以下的數字在t他序列小於5000.

我在印象之下，這需要類似O（logN）的東西，因爲序列的長度很大，這讓我想到了BIT（二進制索引樹 - 因爲查詢），而是一個2D BIT太大，即使在更新端也需要很長時間才能運行。因此，我在這裏看到的唯一解決方案應該是1D BIT或段樹，但我無法弄清楚如何根據這些數據結構制定解決方案。我試圖保留在有序數字集合中的位置，但我無法弄清楚如何創建一個BIT來響應給定表單的查詢。

此外，算法應適合像500ms給定的限制。 編輯1： 500ms的所有對預處理的操作，並回答詢問

編輯2：其中i，j是在序列中的第一和最後一個元素的位置，尋找大於x元素和實施例：： 要有1，3，2，4，6，第3和查詢1，4，3，5，從而1和4位（含）有2之間大於y

EDIT 3小元素（3和4）大於（或等於）3且小於5

預先感謝您！對不起，英文很差！

Answer 1

通過對排序後的子陣列進行BIT組織的數組來實現2D範圍計數。例如，在輸入

[1, 3, 2, 4, 6, 3] 

oracle的將是

[[1] 
,[1, 3] 
,[2] 
,[1, 2, 3, 4] 
,[6] 
,[3, 6] 
]. 

空間用量爲O（N日誌N）（希望細）。如果你小心，構造需要O（N log N）時間，否則O（N log^2 N）時間（沒有理由用於你的應用程序methinks）。

要使用序列索引和值的最大值來回答查詢（其中四個可用於回答輸入查詢），請對最大索引執行BIT讀取過程，使用數組中的二進制搜索來計算元素不超過最大值。查詢時間爲O（log^2 N）。