Jaka struktura danych skutecznie przechowuje zakresy liczb całkowitych?

Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności:

• Wstaw nową liczbę całkowitą
• Wstaw zakres ciągłych liczb całkowitych
• Usuń liczbę całkowitą
• Usuń wszystkie liczby całkowite poniżej liczby całkowitej
• Sprawdź, czy występuje liczba całkowita

Moje dane mają tę właściwość, że często zawierają ciągi liczb całkowitych w kolekcji. Na przykład kolekcja może w pewnym momencie być:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

Najprostszym podejściem jest użycie zrównoważonego drzewa binarnego, takiego jak C ++ std :: set, jednak korzystając z tego, nie wykorzystuję faktu, że często mam serie liczb. Być może lepiej byłoby przechowywać kolekcję zakresów? Oznacza to jednak, że zasięg musi zostać podzielony, jeśli liczba całkowita w jego środku zostanie usunięta, lub połączony razem, jeśli zostanie wypełniona przestrzeń między dwoma zakresami.

Czy istnieją jakieś struktury danych, które byłyby odpowiednie dla tego problemu?

Sugeruję użycie binarnego drzewa wyszukiwania, powiększonego, aby liście mogły zawierać interwał (ciąg kolejnych liczb całkowitych). Zachowaj niezmiennik, aby interwały nie nakładały się i były w porządku (zgodnie z niezmiennikiem drzewa wyszukiwania). (Można to uznać za szczególny przypadek drzewa interwałów lub drzewa segmentów, w szczególnym przypadku, gdy interwały nie nakładają się).

Ta struktura danych umożliwia obsługę wszystkich operacji w czasie , gdzie jest liczbą interwałów. Ponieważ mamy gwarancję , oczekiwałbym, że będzie to dość wydajne. (W szczególności tak, możesz podzielić interwał na dwie części lub połączyć dwa sąsiednie interwały w jeden interwał w czasie .)$O(\lg n)$$n$$n\le 65535$$O(\lg n)$

Po pierwsze, twoje pytanie jest bardzo źle sformułowane, jeśli nie z innego powodu, ponieważ „szybko” niewiele znaczy. Musisz podać dane dotyczące tego, co oznacza „szybki”.

Poza tym, próbując wymyślić projekt problemu, musisz najpierw bardzo dobrze zrozumieć problem i zadać wiele dodatkowych pytań. Odpowiednie pytania w tym przypadku wydają się być (w nieokreślonej kolejności):

• Czy wszystkie te operacje muszą być równie szybkie, czy też niektóre są ważniejsze od innych?
• Czy są inne względy?
• Czy pamięć w ogóle jest problemem?
• Czy zdolność do wstawiania, usuwania i wyszukiwania z wielu wątków stanowi problem?
• Czy obciążenie koncentruje się głównie na wstawianiu? Usuwasz? Patrząc w górę

$[0, 65535]$

Aby uzyskać nieco więcej pracy, możesz zaoszczędzić miejsce, jeśli jest to problem, kosztem szybkości, przechowując dane jako bity w liczbach całkowitych 8192. Chociaż koncepcyjnie pojedyncze operacje na liczbach całkowitych byłyby nadal stałym czasem, a operacje na liczbach całkowitych na dystansie byłyby nadal czasem liniowym, byłyby one wolniejsze.

Więc jeśli to naprawdę twój problem, powinieneś użyć tablicy i przejść do innych, ważniejszych rzeczy z kodem.

$[0, 65535]$

$\mathcal{U}=\{0,\ldots,u-1\}$$O(\log \log u)$

W zależności od struktury danych może istnieć wiele sprytnych alternatyw dla przechowywania danych.