[c.....g]

Jakiś pomysł na strukturę danych, w których sumowanie elementów z pozycji i-tej do j-ej odbywało by się w czasie O(log n)? Dodam do tego, że fajnie jakby wkładanie elementów na dowolną pozycję również odbywało się w podobnej złożoności.
#algorytmika #strukturydanych #algorytmy #programowanie

[c.....o]

@chilling: brzmi jak jakieś diabelskie drzewo

[Szab]

@co_to_sie_stanelo: Na dodatek jak jakieś diabelskie drzewo wyważone.

[c.....g]

@co_to_sie_stanelo: AVL. Pytanie jednak co zrobić, gdy drzewo ważę po pozycji elementy, a dodaje nowy gdzieś np. na pozycji drugiej. Muszę przelecieć całe drzewo i zmienić wszystkim elementom pozycję?

Wtedy dodawanie robi się O(n).

@Szab

[Szab]

@chilling: Ty, ale w ogóle da się tak żeby sumowanie odbywało się w czasie O(log n)? Przecież niezależnie od struktury i tak musisz przelecieć po tych (j-i) elementach.

[c.....o]

@chilling: nie wiem jaki problem rozwiązujesz, ale wiele drzewiastych problemów da się uprościć do słownika "klucz" -> lista wartości. W takiej sytuacji o wiele łatwiej się myśli :)

[c.....g]

@Szab: tak czy siak fajnie jakby wkładanie elementu było O(logn), a sumowanie zajmowało j-i + jakaś tam stała.

[piternet]

@chilling: przecie to zwykłe drzewo przedziałowe, opisane choćby tu http://was.zaa.mimuw.edu.pl/?q=node/9

[pkh]

@chilling: Hm... A moze tak: Robisz normalne drzewo RBT, albo AVL. Tyle ze w nodzie trzymasz dodatkowo sume wartosci mniejszych niz wartosc noda? Wtedy operacja suma pomiedzy i-node i j-node to byly by dwie operacje logn. Troche trzeba by bylo komobinowac napewno przy zachowaniu wywazenia, ale wydaje mi sie ze da rade

[piternet]

@Szab: no jasne że się da, słowo klucz to drzewo ( ͡° ͜ʖ ͡°)

[c.....g]

@piternet: [pytania nie było]

[c.....g]

@pkh: tylko jak wkładać wtedy element na pozycję np. x (między przedziałem i i j). Wszystkie pozycje większe od x się zmieniają - potrzebuje przelecieć po (w najgorszym przypadku) n elementach i zmienić ich pozycję. Złożoność dodania robi się liniowa.

[piternet]

@chilling: tzn? jeśli chodzi ci o wariant, że potrzebujesz operację insert(a, b), która wstawia coś na przedział oraz operację query(a, b), która jakąś wartość ci zwraca (np. sumę z przedzialu), to jest to nieco trudniejsze niż insert(a) a potem query(a,b), ale implementacja jest tam też opisana, w podpunkcie "3. Wariant "przedział-przedział"

[c.....g]

@Szab: mówisz o tablicy haszującej? A co z wkładaniem elementu na miejsce już zajęte? Wtedy tablica haszująca z listą kierunkową?

[Szab]

@chilling: Znalazłem coś takiego: http://en.wikipedia.org/wiki/Skip_list

[c.....g]

@Szab: wiem, ale dla danych gdzie głównie operujesz na "miejscach" a nie wartościach #!$%@? to strasznie do implementacji.

[pkh]

@chilling: Nic nie musisz przekladac. Masz drzewo. Dodajesz nowy element o wartosc A i kluczu X. Drzewo Ci sie balansuje. Ty jedynie musisz sie zatroszczyc o to, zeby przy kazdym dodaniu policzyc jego sume od 0 do jego elementu. Co jest proste, bo poprstu po balansie patrzysz na jege element lewy (reprezentacja ze lewy jest mniejszy, a prawy wieszky) i dodajesz jego wartosc. Potem jak chcesz miec sume i-node i

[Szab]

@pkh: A czy fakt, że wstawiając na k-tą pozycję musisz zaktualizować dodatkowo (n-k) sum nie komplikuje złożoności? Pytam bo jestem ciekaw :D

[pkh]

@Szab: Wydaje mi sie ze nie. Majac drzewo zrownowazone masz zapewnione ze proces dodawania i wyszukiwania jest w czasie logn. Zakladajac ze kazdy node trzyma sume swoich dzieci + swoja wartosc. To znalezienie i-node to jest operacja koszt to logn (znalezienie noda o pozycji x i zwrocenie jest wartosci plus sumy prawego dziecka - masz wtedy sume od i do roota). Potem szukasz j-node. Majac go (koszt logn) zwracasz wartosc