wybór struktury danych

Potrzebuje kontenera, który będzie przechowywał liczby całkowite z zakresu od a do b włącznie bez powtórzeń.

Liczby będą dodawane w dowolnej kolejności i JEDYNĄ informacją, którą potrzebuje z tego kontenera jest ilość liczb, znajdujących się w kontenerze mniejszych od dodanej liczby przy maksymalnej złożoności O(log n)

Dodam, że piszę w C++, i zastanawiałem się nad różnymi strukturami:
vector - trzeba by za każdym razem sortować
set - znajdywanie ilości liczb mniejszych od dodanej liczby jest w czasie liniowym.

Co sądzicie o implementacji np zrównoważonego drzewa binarnego?

vectora nie musisz sortować za każdym razem, wystarczy że będziesz dodawał elementy na zasadzie takiej jak w sortowaniu przez wstawianie. W efekcie masz O(logn) na wyszukanie wartości w posortowanym wektorze, O(1) na policzenie ile jest elementów mniejszych (arytmetyka iteratorów) i O(logn) na wstawianie elementów do zbioru (trzeba sprawdzić czy elementu w zbiorze nie ma i ew znaleźć miejsce gdzie element ma być), przy czym w przypadku wstawiania nie biorę pod uwagę potrzeby przesuwania pozostalych elementów :P

Potrzebujesz tego do zadania na OI czy jestem przewrażliwiony?
Propozycja - interval tree, przy czym w elementach drzewa przechowujesz nie listę zawieranych zakresów tylko ich ilość. Dodawanie liczby n implementujesz jako dodanie zakresu (0; n).

Wektor o długości (b-a+1) w którym przechowujesz liczbę elementów mniejszych.
Dla elementu

Czyli dla
a = 0
b = 3
i zbioru [2,3]
wektor
[1] = 0,
[2] = 0,
[3] = 1
[4] = 2

Liczba elementów mniejszych od 3 = v[3-1] (złożoność O(1))

Dodanie wartości 1 => powiększenie wszystkich elementów o indeksie >= 1 (złożoność O(n))
[1] = 0,
[2] = 1,
[3] = 2
[4] = 3

Dajcie znać czy gdzieś się rąbnąłem, bo to tak na szybko.
Ograniczenie na złożoność tyczy się wszystkich operacji czy tylko wyszukiwania?

Drzewo turniejowe. W każdym węźle będziesz przechowywał ile liści jest aktywnych, a więc wartość w rodzicu == suma wartości w dwóch dzieciach. Dodanie/ usunięcie liczby to Theta(log n), policzenie ilości aktywnych liści w zakresie to też Theta(log n). Zajętość pamięci = 2 * ilość liści, czyli 2 * (b - a + 1). Generalnie drzewo turniejowe to banalna struktura, nie ma żadnych wskaźników, indeksów, ani innych duperelów, a jest przydatne w wielu sytuacjach.

człowiekowi niosącemu młotek wszystko przypomina gwóźdź :-)
prawie wszystko można prasnąć gdy ma się młot jak Thor (dygresja taka)

ja już wpadłem na rozwiązanie w dniu pytania, jest w komentarzu w tym wątku oraz pytanie o nazwe tej struktury tutaj:
Nazwa struktury

zrobiłem to tak:

• wszystko przechowuje w drzewie które wewnętrznie jest tablicą
• samych elementów bezpośrednio nie przechowuje, przechowuje jedynie ilości elementów po lewej stronie.

pokaże na przykładzie, nie chce mi się dokładnie opisywać:

liczby w kółkach czarnych są jedynie pomocnicze, zielone liczby oznaczają jakie wartości przechowuje dany wierzchołek (czy tam rodzic), liczby w czerwonych kółkach symbolizują liczby dodane do struktury. Gdy chcę dodać element, to gdy dodaje element gdzieś po lewej stronie danego rodzica to dodaje do niego jeden. gdy sprawdzam ile liczb jest po lewej stronie dodaje tylko liczby z rodzica jeśli idę w drzewie w prawo

Nota bene:
Warunek, że liczby się nie powtarzają chyba nie jest niezbędny. Struktury powinny działać nawet jak są powtórzenia.