Witam, napisałem sobie wg. mnie ciekawą implementacje kontenera i zastanawia mnie czy już wcześniej ktoś coś takiego wymyślił i czy posiada on jakąś nazwę, działa podobnie do multiset-a, z tym, że daje możliwość w czasie logarytmicznym sprawdzenia ilości mniejszych od niego elementów:
- przechowuje elementy jedynie z zadanego na początku przedziału
<``a,b``>
(dla ułatwienia opisu dalej przyjmę zam=b-a+1
,ilość elementów = n
), - w dowolnym momencie można znaleźć ilość elementów po lewej
O(log n)
, - dodawanie elementów, usuwanie elementów (w tym samym czasie można dodać/odjąć dowolną ilość tych samych elementów)
O(log n)
, - znalezienie i-tego elementu
O(log^2 n)
, - iteracja po wszystkich elementach:
O(n log^2 n)
lubO(m+n)
, - sprawdzenie ilości dowolnego z elementów
O(log n)
EDIT:
złożoność pamięciowa:
między m
, a najbliższą potęgą dwójki większą od m