[hawking300]

Hej mirki, macie moze pomysl na dynamiczna strukture ktora wykona ponizsze operacje w czasie log n?
Wstaw(a, i) - wstaw element a jako i-ty
Usun(i) - usun i-ty element ciagu.
Podaj(i) - podaj i-ty element ciagu.

Ogolnie wiadomo, jak mamy podac k-ty element ale co do wielkosci to latwo jest to zrealizowac na drzewach Splay/AVL. Wystarczy pamietac ile elementow jest w naszym lewym poddrzewie i w naszym prawym poddrzewie. Tutaj mamy powiedziane wstaw element o wartosci a na i-tej pozycji wiec nie mozna mowic o porzadku. Moglibysmy miec zrownowazone drzewo sortowane wedlug pozycji, ale jesli np. mamy n elementow i wstawimy element na pozycji 2 to musimy zwiekszyc wszystkie klucze o wartosci wiekszej od 2, wiec wydaje sie to slabe. Jakies pomysly? Moze nie jest to mozliwe w czasie log n?

#programowanie #naukaprogramowania

[k.....v]

@hawking300: w modelu PRAM jest to banalne ( ͡° ͜ʖ ͡°)

[hawking300]

@kolesnikov: znalazlem
https://en.wikipedia.org/wiki/Rope_%28data_structure%29

[k.....v]

@hawking300: dzięki :)
Dobrego algo nigdy za mało