高效的數據結構

Question

我有一組不相交的整數區間，並要檢查一個給定的整數是否位於這些區間中的一個。當然，這可以通過在對數時間進行二分搜索來實現。然而，絕大多數查詢返回false，即只有非常少的整數位於任何區間。爲了加速應用程序，我正在尋找一種概率，恆定時間算法（某種散列函數），告訴我給定的整數是否肯定不是或可能在一個區間內。這裏是預期的算法，其中magic_data_structure與存儲在tree間隔被初始化的草圖：

x = some_integer; 
if(!magic_data_structure.find(x)) 
    return false; // definitely not in any interval 
return tree.find(x); // binary search on tree 

文學任何想法或提示？非常感謝您的幫助！

P.S .:是否有人知道間隔樹的改進？非重疊間隔（與上述不同）可能包括其他間隔？

Answer 1

這是一個天真的解決方案，但不變。

如果你沒有處理大量的數字，你可以使用一個散列表，其中的鍵是數字，值是一個指向它們的集合的指針。但是當然如果有一個很多數據可能需要太長時間（並且內存太多）以這種方式對其進行索引。

貌似有各種disjoint-set data structures and algorithms存儲/檢索他們，但如果其中任何一個有恆定的時候，我懷疑。