Struktura danych dla zakresów

Potrzebuje wydajnej struktury danych do przeszukiwania rangeów (zakresów).
Tzn przechwouje w kontenerze zakresy powiedzmy [0;1], [2,4] i taki kontener ma mi powiedzieć do którego zakresu należy liczba 3. Zakresy są dyskretne i rozłączne.

Zwykłe drzewa poszukiwań można zmodyfikować, żeby wstawiały i wyszukiwały takie zakresy w czasie O(log n). Ale w mojej aplikacji sytuacja wygląda tak, że wstawianie powinno być bardzo wydajne (najlepiej O(1)). Operacja wyszukiwania jest robiona dosyć rzadko, ale na taką operacje składa się wyszukiwanie wielu liczb. Najprostsze rozwiązanie to stworzyć zwykły wektor. Przed operacją wyszukiwania posortować go i użyć szukania binarnego. Drzewa BST raczej odpadają ze względu na zbyt długi czas wstawiania.
Ktoś coś wie o jakimś algorytmie/strukturze danych która była by bardziej wydajna? Może jakaś modyfikacja HashMapy (odpowiednia funkcja haszująca?) lub połączenie kilku struktur danych?

Struktura danych, która może okazać się przydatna to drzewa zakresów (ang. Range Tree). Dla przypadku dwuwymiarowego:

Build Time: O(n)
Space: O(n)
Query Time: O(log(n) + t)

Tu znajdziesz przykładową implementację w C#: http://www.emilstefanov.net/Projects/RangeSearchTree.aspx

Jako że zakresy są rozłączne problem jest analogiczny do przechowywania zwykłych liczb całkowitych. Z tym, że hashmapa w tym przypadku odpada bo nie pozwala na operacje lower/upper bound tj. "znajdź największą nie większą niż x". Bo rozumiem, że podczas wstawiania przedziały mogą się nakładać i wtedy je będziesz łączyć?
W ogólnym przypadku nie zrobisz tego szybciej niż log(n).
BST będzie chyba najlepsze, operacja wstawiania kosztuje tyle co wyszukanie czyli O(log(n)). Właśnie przy posortowanym wektorze byłby problem, bo musiałbyś przesuwać elementy o jedno miejsce w prawo aby wstawić nowy, czyli wyszłoby O(n*log(n)).

Może i dałoby się tu coś przykombinować, ale nie jeśli chodzi o ogólny przypadek, musiałbyś wyszukać jakieś charakterystyczne cechy tych danych i je wykorzystać.

BST i range tree niestety mi się nie opłacają bo w moim przypadku wstawianie stanowi wąskie gardło. Przeszukiwanie w mniejszym stopniu.
Dane są rozłączne bo taka ich natura ;) Nawet nie musze scalać zakresów bo na pewno nie dostanę czegoś nierozłącznego. Moje dane to bloki pamięci przydzielane przez system operacyjny. Masz zapewne racje, że w ogólnym przypadku nie da się szybciej ale jednak w moim szczególnym przypadku jest to możliwe. Znalazłem coś takiego: http://www.hpl.hp.com/personal/Hans_Boehm/gc/tree.html
Dzięki za odpowiedzi.

jeśli są to zwykłe liczby całkowite, ich zakres nie jest bardzo duży to jest sposób by osiągnąć O(1).
Tworzysz bezczelnie tablicę indeksów przedziałów dla danych wartości. By zaoszczędzić na pamięci (taka tablica może być wielka), wartość do odszukania w przedziałach można obdzielić przez jakąś liczbę, wówczas stworzona tablica wskazuje orientacyjny indeks przedziału.

rnd napisał(a)

Dane są rozłączne bo taka ich natura ;) Nawet nie musze scalać zakresów bo na pewno nie dostanę czegoś nierozłącznego. Moje dane to bloki pamięci przydzielane przez system operacyjny.
W takim wypadku to odkładaj na koniec wektora i sortuj podczas wyszukiwani, tak jak pisałeś.
Posortuj nowe elementy i scal ze starymi, już posortowanymi. Podczas scalania możesz od razu wyszukiwać.

Z tym że tutaj cała "siła" idzie w dodawanie elementów, być może zbyt dużym kosztem na pozostałe operacje. Żeby nieco bardziej zrównoważyć obliczenia na pozostałe przypadki można połączyć drzewo i wektor tj. zrobić drzewo wektorów, np. drzewo binarne o niedużej, odpowiednio dobranej wysokości, kopiec by się do tego nadał. Każdy węzeł niech odpowiada za pewien przedział ustalany dynamicznie tak aby rozłożyć elementy w miarę równomiernie.

Nie wiem czy się nadaje ale jest coś takiego: http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
Niedługo poczytam o tym dokładniej :)

Zakładam, że używasz 32-bitowych liczb całkowitych.

Przy zrównoważonym drzewie zakresowym wstawianie i wyszukiwanie ma koszt O(log n)=O(log N)=O(log 2^32)=O(32).

Jeżeli chcesz zmniejszyć czas wstawiania/wyszukiwania, to użyj LASU drzew zakresowych.

Stwórz tablicę drzew zakresowych (AVL + RANGE) długości np. 2^16.

Przy wyszukiwania nałóż maskę na 16 najbardziej znaczących bitów liczby, weź z tablicy odpowiednie drzewo i dalej wyszukuj normalnie.

Przy wstawianiu podobnie - bierzesz odpowiednie drzewo i wstawiasz do niego. Problemem są tylko przedziały, które są w więcej niż jednym drzewie. Należy je wstawić do każdego z drzew, któremu odpowiada chociaż części dodawanego przedziału. Nie jest to jednak duży problem, gdyż przedziały się nie przecinają, więc będzie co najwyżej 2^16-1 przedziałów zawierających więcej niż jedno drzewo.

W ten sposób operacje wstawiania i wyszukiwania będą średnio o połowę tańsze niż w przypadku jednego dużego drzewa.