[Algorytmy] Implementacja dynamicznego zbioru

[matematyka464]

Witam,
Chcę zastanowić się nad czymś takim:
Mamy n elementowy ciąg liczb. Możemy zechcieć w i-te miejsce wstawić jakąś liczbę, a potem zapytać o sumę na przedziale \(\displaystyle{ \left[ i...j \right]}\), \(\displaystyle{ i=1,2...,n+1}\).
Czyli widać, że wstawienie w dane miejsce "rozsuwa" ciąg.
Np, powiedzmy że mamy już:
\(\displaystyle{ 1\ 4\ 67\ 7\ 212}\)
Wstawiamy w \(\displaystyle{ i=3}\) wartość \(\displaystyle{ 10}\)

\(\displaystyle{ 1\ 4\ 10\ 67\ 7\ 212}\)
I teraz suma na przedziale np. \(\displaystyle{ \left[ 2..3 \right] =14}\)
Każda z tych operacji (Wstawienie i sumowanie) ma być w czasie \(\displaystyle{ \log \left( n \right)}\)

Jak można to wykonać stosując drzewa avl ?

[Zordon]

Zastanów się najpierw nad prostszą wersją, tj. utrzymujesz listę i możesz
- wstawić element na pozycję \(\displaystyle{ i}\)
- zapytać o wartość elementu na pozycji \(\displaystyle{ i}\)
Obie operacje w czasie \(\displaystyle{ \log (n)}\).
Tu jest ukryta idea, zrobienie tych sum już jest potem proste.

[matematyka464]

Nie mam polskich znakow - z gory przepraszam.
Ok, mam chyba pewien pomysl. Na razie na etapie idei, jak bedzie ok to przedstawie kod.
Uzywal bede drzew AVL. W kazdym wezle bede pamietal licznosc tego poddrzewa. Po co mi to ?
A wartosc kazdego wezla to para: (nr w ktory go wstawiano, wartosc wstawiona). Kluczem jest numer.
Wstawianie jak do normalnego drzewa AVL + aktualizacja licznosci poddrzewa.
I teraz podczas szukania wartosci dla \(\displaystyle{ i}\)-tego postepujemy nastepujaco:
Np. \(\displaystyle{ i = 5}\), zakladam ze jest nie mniej elementow.
Patrze na lewego syna - jesli licznosc poddrzewa jest wieksza(rowna) niz \(\displaystyle{ 5}\) to schodz tam. Jesli nie, to schodze do prawego, ale wtedy juz szukam \(\displaystyle{ 5-licznosc(lewy)}\). I tak schodze i schodze albo do momentu gdy zzeruje \(\displaystyle{ i}\), albo gdy doszedlem do liscia.

Tak samo moge trzymac sume z poddrzewa. Jak policzyc sume przedzialu jeszcze nie wiem, ale czekam na ocene dotychczasowego -- 29 gru 2014, o 23:55 --Hmm, sume przedzialu\(\displaystyle{ [a;b]}\) mozna by chyba tak:
\(\displaystyle{ SUMA(korzen) - SUMA(\le a) - SUMA (\ge b)}\)

[Zordon]

Tak, to jest właściwa idea.

[matematyka464]

Ok, więc zobacz surowo na to
sum_upper nie pisałem, bo nie to symetryczne do sum_lower.

Kod: Zaznacz cały

AVLtree t;
root = t.root;
empty (S){
	init t;
	S = t;
}

insert (S, i, x){
	insert_(S, i, x, root);
}
insert_ (S, i, x, v){
	|normalne wstawianie jak przy AVL
	|gdy juz zostala wykonana (badz nie) rotacja
	|aktualizujemy nasze wartosci
	|przjmuje ze count(NULL) = sum(NULL) = 0
	v.count_ = v.count_ + count(lewy(v)) + count(prawy(v));
	v.sum_ = v.sum_ + sum(lewy(v)) + sum(prawy(v));
}

at (S, i){
	if i > root.count_ then
		raise INV_A;
	at_(S, i, root);
}
at_ (S, i, v){
	if is_leaf (v) then
		return v.value;
	if i = 0 then
		return v.value;
	if count(lewy(v)) >= i
		return at_ (S, i, lewy(v));
	else
		return at_ (S, i - count(lewy(v)), prawy(v));
		
}

sum (S, i, j){
	root.sum_ - sum_lower (S, i, root, 0) - sum_upper (S, j, root, 0);
}
sum_lower (S, i, v, acc){
	if i = 0 then return acc
	if v.nr <= i then 
		if count(lewy(v)) <= i then
			return sum_lower (S, i - count(lewy(v)), prawy(v), acc + sum (lewy(v));
		else
			return sum_lower (S, i, lewy(v), acc);
	else
		return sum_lower (S, i, lewy(v), acc);
}

-- 5 sty 2015, o 13:30 --Nikt nie sprawdzi ?