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ę za m=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) lub O(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