różnica/suma/itd dwóch posortowanych zbiorów w lg n

Kojarzy ktoś jakiś inteligentny sposób na obliczenie symetrycznej różnicy między dwoma posortowanymi zbiorami (np. w drzewie binarnym) o złożoności pesymistycznej mniejszej niż O(n)? - dokładniej, między częścią posortowanych zbiorów (np. elementy 10-10k z A, 50-80k z B). Struktura danych, algorytm, ...
Zarówno przejrzenie książek, jak i krótkie poszukiwania w internecie nie przyniosły rezultatu. Widzę możliwe mniejsze ograniczenia dla specyficznych danych (np. gdy wiemy, że jeden zbiór zawiera się w drugim) oraz sposoby na zejście blisko lg n w średnim przypadku (zawieranie się, drzewo z hashowanymi z zakresami, itd), jednak ciągle zostaje ten pesymistyczny liniowy przypadek.
Wydaje mi się to niemożliwe, jednak w przypadku algorytmiki należy uważać z pewnością :)

P.S Przetwarzanie wstępne może być nawet tragiczne (sześcian) - danymi są dwa (albo więcej, jednak dwa to przypadek podstawowy) posortowane zbiory zmieniające się bardzo rzadko - wyszukiwanie jest głównym problemem.

Da się. Przerobione drzewo przedziałowe, zaimplementowałem kiedyś takie. Złożoność n*log(n). Jednak to strasznie dużo opisywania, musiałbym z kilka rysunków i schematów zrobić, żeby wyjaśnić :P może ktoś łatwiejszy sposób znajdzie.

Spykaj napisał(a)

Przerobione drzewo przedziałowe, zaimplementowałem kiedyś takie. Złożoność n*log(n).

złożoność -czego?- podałeś? budowy drzewa?

Nom budowy drzewa :P poczekaj, to zapomnij o tym xD chyba źle zrozumiałem twój post :P

Jeśli chcesz wyznaczyć całą różnicę symetryczną i ją wypisać, to nie ma najmniejszych szans na złożoność log(n). W końcu wszystkie elementy musisz znaleźć, a samo ich znalezienie to już O(n), co najwyżej złożoność może być tylko gorsza, jeśli wyszukiwanie kolejnych elementów byłoby trudne, ale skoro są obok siebie (ciąg jest posortowany), no to po prostu O(n).

Jeśli natomiast chciałbyś szybko ilość elementów w różnicy symetrycznej, to w drzewie przedziałowym, miałbyś ją w czasie O(1), zbudowanie drzewa n*log(n), a zmiana czegoś w drzewie log(n). Jeśli o ten przypadek by ci chodziło, to wtedy się zgłoś.

Ale dlaczego tak skomplikowanie?

Zakładając, że mamy dane posortowane, można to zrobić w banalny sposób w czasie O(n) na zwykłych tablicach.

Oto przykład w pseudokodzie.
Wygląda bardzo podobnie do scalania tablic z mergesorta.

t1[0..N1-1]
t2[0..N2-1]

i1=0
i2=0
wynik={}
while (i1<N1 && i2 <N2){
 w1=t1[i1];
 w2=t2[i2];
 if (w1==w2){
    i1++;
    i2++;
 } else if (w1<w2){
   wynik.dodaj(w1);
  i1++;
 } else{
   wynik.dodaj(w2);
  i2++;
 }
} 

while (i1<N1){
   wynik.dodaj(t1[i1++]);
}

while (i2<N2){
   wynik.dodaj(t2[i2++]);
}

Ciekawi mnie kiedy niektórzy nauczą się czytać ze zrozumieniem, chyba nigdy. Chodzi przede wszystkim o róźnicę zbiorów i wyłącznie w złożoności mniejszej od O(n). Przypadek scalania w O(n) jest autorowi chyba dobrze znany skoro szuka lepszego rozwiązania, nie? A 'pseudokodu' bardziej czytelnie już napisać się nie dało...

hm.. ciekawy problem.. na pewno dokladnie okresliles zadanie? jesli masz dwa zbiory A i B z ktorych masz wziac losowe dwa zakresy i z nich obliczyc roznice to ciezko.. jedyne co mi na mysl przychodzi to podczas owego wstepnego przetwarzania wykonac CAŁOŚĆ pracy porownawczej i przechowac ja wraz z czesciowymi informacjami o pozycjach krytycznych wplywajacych na wynik i potem na żądanie zwrocenia różnicy miedzy ai..aj <-> bx..by zwrocic ow wynik inteligentnie rozszerzony o elementy spoza zakresu?

chodzi pewnie o zadanie mozaikowatość z potyczek algorytmicznych, czyż nie??

http://www.konkurs.adb.pl/user.phtml/moz.pdf?op=get&id=206