Cześć,
Czy ma ktoś pomysł jak znajdywać parę elementów różniących się o dokładnie d (d nie jest ustalone, jest dane) ? Tzn taką parę (a,b), że |a-b| = d
Co więcej, możemy przyjąć, że elementy są dane w drzewie zrównoważonym (może być jakiekolwiek). Możemy też to drzewo ubogacać o co chcemy (byle aktualizować to w czasie stałym). W czasie O(n) potrafię. Da się lepiej ?
0
0
Nie bardzo rozumiem co masz znaleźć w czasie O(n). Masz znaleźć dowolną taką parę w drzewie? To chętnie zobaczę jak to robisz w czasie liniowym, bo jak dla mnie to poniżej O(nlogn) nie zejdziesz bo dla każdej potencjalnej liczby (O(n)) musisz sobie poszukać tej drugiej w czasie logarytmicznym (O(logn)) czyli w sumie wychodzi nam O(nlog).
0
@xawery Ale sformułuj ten problem sensownie, dobra? Bo nikt nie wie czy masz już to drzewo, czy je budujesz, jakie są dane, jakie operacje są na tym drzewie dozwolone. Krótko mówiąc: zaktualizuj swoją "specyfikację" tak, aby nie był to kompletny chaos.
0
Wygląda mi to na zadanie z main.edu.pl :D
Ja je zrobiłem na secie. Miałem policzoną liczbę par że |a-b|=d i dodając dany element (x) do zbioru sprawdzałem czy jest w zbiorze element x-d i x+d. Podobnie przy odejmowaniu. Jak to to, to powodzenia.