• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Modyfikacja drzewa przedział-przedział

Aruba Cloud VPS - 50% taniej przez 3 miesiące!
0 głosów
1,341 wizyt
pytanie zadane 2 marca 2023 w C i C++ przez polandonion Dyskutant (7,560 p.)
edycja 3 marca 2023 przez polandonion
Wie ktoś, czy jeśli mam zbudowane drzewo przedziałowe przedział-przedział typu (+, suma), czyli dodaje na przedziale i odczytuje sume na przedziale, to jeśli potrzebuje drzewo typu (+, max) albo (+, min), albo inną łączną oprację na przedziale, np. jakieś nwd, nww, XOR etc...... to jak zmienić tą strukturę, aby odpowiadała na te zapytania?

ps. dodam, ze jesli chodzi o przedzial-przedzial, to jestem swiezakiem, dwa dni temu sie tego nauczylem i zdazylem zrobic moze z jedno zadanko na (+, suma) i to tyle, i dlatego pytam o takie sprawy
komentarz 2 marca 2023 przez tkz Nałogowiec (42,020 p.)
Nigdy tego jakoś bardzo nie implementowałem, ale teorie kojarzę.

Aby zmienić drzewo przedziałowe typu (+, suma) na drzewo typu (+, max) lub (+, min), musisz zmodyfikować sposób przetwarzania wierzchołków drzewa.

W przypadku drzewa (+, max), zamiast sumować wartości na przedziale, wierzchołek drzewa powinien przechowywać maksymalną wartość na danym przedziale. W ten sposób, zapytanie o maksymalną wartość na przedziale zostanie rozwiązane przez odczytanie wartości wierzchołka drzewa. Aby zmodyfikować drzewo (+, suma) na drzewo (+, max), wystarczy zmienić wartości początkowe wierzchołków drzewa (domyślnie ustawione na 0) na wartości elementów tablicy wejściowej.

W przypadku drzewa (+, min), analogicznie do drzewa (+, max), wierzchołek drzewa powinien przechowywać minimalną wartość na danym przedziale. Zmiana wartości początkowych wierzchołków drzewa na wartości elementów tablicy wejściowej przekształci drzewo (+, suma) w drzewo (+, min).

Jeśli chcesz zastosować inną łączną operację na przedziale, taką jak nwd, nww lub XOR, musisz zmodyfikować funkcję łączącą używaną do łączenia wyników z poddrzew. Należy dostosować funkcję łączącą w taki sposób, aby odpowiadała wymaganiom danej operacji łączącej.

W przypadku operacji nwd i nww, funkcja łącząca powinna zwracać odpowiednio największy wspólny dzielnik lub najmniejszą wspólną wielokrotność wyników z poddrzew. Aby zmienić drzewo (+, suma) na drzewo obsługujące operacje nwd lub nww, należy zmodyfikować funkcję łączącą w taki sposób, aby zwracała nwd lub nww wyników z poddrzew.

W przypadku operacji XOR, funkcja łącząca powinna wykonywać operację XOR na wynikach z poddrzew. Aby zmienić drzewo (+, suma) na drzewo obsługujące operację XOR, należy zmodyfikować funkcję łączącą w taki sposób, aby zwracała wynik operacji XOR na wynikach z poddrzew.

W każdym przypadku, zmiana drzewa przedziałowego wymaga zmiany funkcji łączącej oraz dostosowania wartości początkowych wierzchołków drzewa. Ale to tylko teoria, niech ktoś bardziej doświadczony się wypowie.
komentarz 2 marca 2023 przez polandonion Dyskutant (7,560 p.)
dzięki wielkie :D, jutro to zaimplementuje i dam znać czy się udało
komentarz 3 marca 2023 przez Whistleroosh Maniak (57,360 p.)
edycja 3 marca 2023 przez Whistleroosh

@tkz, to by się zgadzało dla drzew w których modyfikuje się wartość w punkcie i odpytuje na przedziale. Jeśli trzeba dodatkowo modyfikować wartość na przedziale to trzeba też umieć updatować wynik dla przedziału na podstawie tego jak zmodyfikowaliśmy przedział. Np. jeśli jakieś poddrzewo trzyma nwd wierzchołków na przedziale (powiedzmy równe x) i dodajemy 5 do tego przedziału to musimy wiedzieć jak to x się zmieniło ale jedyne informacje jakie posiadamy to to, że dodaliśmy 5 i ile jest wierzchołków na przedziale. Tego się nie da chyba zrobić więc drzewo przedział-przedzial nwd zrobione tą metodą nie jest mozliwe (natomiast da się takie drzewo zrobić, tylko trzeba trzymać inną informacje na przedziale)

komentarz 3 marca 2023 przez polandonion Dyskutant (7,560 p.)

no właśnie jakoś nie mogłem rozkminić tego pomysłu @tzk. A ty, @Whistleroosh, masz jakiś sensowny pomysł na  drzewo (+, max) albo (+, min)? Chodzi mi o samą teorię. Próbuję zrobić zadanie Koleje i nie wiem właśnie czy tam nie będzie właśnie taka struktura jak drzewo przedział-przedział typu (+, max).

komentarz 3 marca 2023 przez Whistleroosh Maniak (57,360 p.)
Jak masz drzewo (+, suma) to łatwo powinno dać się zamienić na (+, max). Jakbyś dał kod to łatwiej by mi było powiedzieć co trzeba zmienić, bo samo drzewo przedział-przedział można róznie implementować. A zadanie Koleje można jak najbardziej zrobić tym drzewem
komentarz 3 marca 2023 przez polandonion Dyskutant (7,560 p.)

Takie coś wyklepałem:

#include <iostream>
#include <string>

using namespace std;

// tree[v] - drzewo sum przedziałowych
// lazy[v] - to, co muszę przekazać każdemu z dzieci
//           podczas query, albo update
int tree[150000], lazy[150000];

// p - poczatek zapytania, k - koniec zapytania
// q - pomocnicza zmienna, ktora wskazuje na indeks
//     o jeden mniejszy od pierwszego liścia
int p, k, q;

// add() - funkcja dodająca val na przedziale [p, k]
void add(int v, int a, int b, int val) {	
	if (k < a or b < p)
		return;
	else if (p <= a and b <= k) {
		tree[v] += (b - a + 1) * val;
		lazy[v] += (b - a + 1) * val / 2;
	}
	else {
		int l = v * 2, p = v * 2 + 1, mid = (a + b) / 2;

		tree[l] += lazy[v];
		tree[p] += lazy[v];
		lazy[l] += lazy[v] / 2;
		lazy[p] += lazy[v] / 2;
		lazy[v] = 0;

		add(l, a, mid, val);
		add(p, mid + 1, b, val);

		tree[v] = tree[l] + tree[p];
	}
}

// sum() - odpowiada na zapytanie o sumę na przedziale [p, k]
int sum(int v, int a, int b) {
	if (k < a or b < p)
		return 0;
	else if (p <= a and b <= k)
		return tree[v];
	else {
		int l = v * 2, p = v * 2 + 1, mid = (a + b) / 2;

		tree[l] += lazy[v];
		tree[p] += lazy[v];
		lazy[l] += lazy[v] / 2;
		lazy[p] += lazy[v] / 2;
		lazy[v] = 0;

		return (sum(l, a, mid) + sum(p, mid + 1, b));
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// n - ilosc elementow
	// m - ilosc zapytan
	int n, m;
	cin >> n >> m;

	// prawidlowe ustawienie pomocniczej zmiennej q na
	// wartosc o 1 mniejsza od pierwszego liscia drzewa
	q = 1;
	while (q < n)
		q *= 2;
	q --;

	// wczytywanie kolejnych zapytan
	while (m --) {
		string str;
		cin >> str;

		if (str == "dodaj") {
			int a, b, val;
			cin >> a >> b >> val;

			// poprawne ustawienie krancow przedzialu
			p = q + a, k = q + b;
			add(1, q + 1, q + n, val);
		}
		else {
			int a, b;
			cin >> a >> b;

			p = q + a, k = q + b;
			cout << sum(1, q + 1, q + n) << ' ';
		}
	}
}

 

komentarz 3 marca 2023 przez Whistleroosh Maniak (57,360 p.)

Ja wolę implementację drzewa przedział-przedział w której funkcja przesuwająca wartości w lazy jest w oddzielnej funkcji, bo wtedy jest dużo czytelniej i łatwiej zapanować nad tym co się dzieje. Tak jak tutaj

Ale z tego co widzę to na pewno w linii 36. powinien być min. W 21 i 22 nie trzeba teraz mnozyć przez długość przedziału i dzielić przez 2. Tak samo w 29 i 30 nie trzeba dzielić przez 2. Funkcję sum analogicznie

komentarz 3 marca 2023 przez polandonion Dyskutant (7,560 p.)
edycja 3 marca 2023 przez polandonion

o ile podmianka linii 36. oraz przeniesienie aktualizacji tree[] oraz lazy[] wydaje mi się bardzo logiczne, o tyle nie wiem co dalej... wsensie ok, wracając tą rekurencją to jest oczywiste, że zamiast sumować, będę zapisywał max / min, ale nie wiem, czego mam dokonać, jeśli metoda update niejako "rozdwaja mi się na dwa przedziały" wtedy jak mam zaktualizować synów aktualnego wierzchołka v?

Tutaj z'update'owana wersja poprzedniego kodu z małą poprawką (dodałem własną metodę push()), aby łatwiej Tobie (i nawet mi) się go czytało. Tam gdzie napisałem '???' oznacza, że właśnie nie wiem co mam w tamtym miejscu zrobić.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// tree[v] - drzewo sum przedziałowych
// lazy[v] - to, co muszę przekazać każdemu z dzieci
//           podczas query, albo update
int tree[150000], lazy[150000];

// p - poczatek zapytania, k - koniec zapytania
// q - pomocnicza zmienna, ktora wskazuje na indeks
//     o jeden mniejszy od pierwszego liścia
int p, k, q;

// push() - medota aktualizująca tree[] oraz lazy[]
void push(int v, int l, int p) {
	/* tree[l] += lazy[v];
	tree[p] += lazy[v]; */

	lazy[l] += lazy[v] / 2;
	lazy[p] += lazy[v] / 2;

	lazy[v] = 0;
}

// add() - metoda dodająca val na przedziale [p, k]
void add(int v, int a, int b, int val) {	
	if (k < a or b < p)
		return;
	else if (p <= a and b <= k) {
		/* tree[v] += (b - a + 1) * val; */ // ???
		lazy[v] += (b - a + 1) * val / 2; // ???
	}
	else {
		// l - lewy syn aktualnego wierzchołka, p - analogicznie prawy
		// mid - środek przedziału, w za który odpowiada wierzchołek v
		int l = v * 2, p = v * 2 + 1, mid = (a + b) / 2;

		push(v, l, p);

		add(l, a, mid, val); // ???
		add(p, mid + 1, b, val); // ???

		tree[v] = max(tree[l], tree[p]);
	}
}

// getMax() - odpowiada na zapytanie o max'a na przedziale [p, k]
int getMax(int v, int a, int b) {
	if (k < a or b < p)
		return 0;
	else if (p <= a and b <= k)
		return tree[v];
	else {
		// l - lewy syn aktualnego wierzchołka, p - analogicznie prawy
		// mid - środek przedziału, w za który odpowiada wierzchołek v
		int l = v * 2, p = v * 2 + 1, mid = (a + b) / 2;

		push(v, l, p);

		return max(getMax(l, a, mid), getMax(p, mid + 1, b));
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// n - ilosc elementow
	// m - ilosc zapytan
	int n, m;
	cin >> n >> m;

	// prawidlowe ustawienie pomocniczej zmiennej q na
	// wartosc o 1 mniejsza od pierwszego liscia drzewa
	q = 1;
	while (q < n)
		q *= 2;
	q --;

	// wczytywanie kolejnych zapytan
	while (m --) {
		string str;
		cin >> str;

		if (str == "dodaj") {
			int a, b, val;
			cin >> a >> b >> val;

			// poprawne ustawienie krancow przedzialu
			p = q + a, k = q + b;
			add(1, q + 1, q + n, val);
		}
		else {
			int a, b;
			cin >> a >> b;

			p = q + a, k = q + b;
			cout << getMax(1, q + 1, q + n) << ' ';
		}
	}
}

 

komentarz 3 marca 2023 przez Whistleroosh Maniak (57,360 p.)
W Twoim kodzie jest trochę inaczej niz u mnie, bo lazy[v] u Ciebie słuzy do zupdatowania drzew tree[l] i tree[r] podczas gdy u mnie updatuje tylko tree[v]. Ale jesli chcesz zrobić w ten sposób to w push dajesz to tree[l] += lazy[v] i tak samo tree[r]. Linijki 22 i 23 bez dzielenia przez 2. W 33 i 34 do tree i lazy robisz += val. Możliwe że coś pominąłem, ale to się okaże
komentarz 3 marca 2023 przez polandonion Dyskutant (7,560 p.)
Wygląda na to, że działa. Nie rozumiem jednak sposobu działania tego drzewa. Jeśli mógłbyś wyjaśnić, za co w przypadku tego drzewa odpowiada tree[v] oraz lazy[v]. Z góry dzięki :D
komentarz 3 marca 2023 przez Whistleroosh Maniak (57,360 p.)
tree[v] działa tak jak w innych drzewach. W tym przypadku trzyma max na przedziale (być może nieaktualny max). lazy[v] trzyma wszystkie "pending updates" czyli pamięta ile dodałeś do tego poddrzewa v od ostatniego czasu gdy je odwiedziłeś. I teraz jak odwiedzasz sobie poddrzewo v i w chodzisz do jego lewego i prawego poddrzewa to oczywiście musisz dodać lazy[v] do tree[l] i tree[r] bo ich max być może się zdezaktualizował od czasu ostatnich odwiedzin (jeśli max w poddrzewie to y a dodałeś x do tego poddrzewa to maks to terax x + y, w tym przypadku y = tree[l], x = lazy[v]). No i musisz zrobić lazy[l] += lazy[v] (tak samo r) bo to lewe i prawe poddrzewo muszą powiedzieć później swoim poddrzewom żeby też zaktualizowały maksa
1
komentarz 3 marca 2023 przez polandonion Dyskutant (7,560 p.)
rozumiem, dzięki za wytłumaczenie. A tak btw udalo mi sie uzyskać 100% z Koleje dzięki tej sztuczce jakim jest drzewo przedziałowe :D

1 odpowiedź

+1 głos
odpowiedź 19 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
wybrane 22 marca 2023 przez polandonion
 
Najlepsza
W godzinę można się nauczyć drzew przedział-przedział:

- dodaj na przedziale i odczytaj sumę na przedziale itp.

- dodaj na przedziale i odczytaj maxa na przedziale itp.

https://www.youtube.com/watch?v=eIpx8zOuJDE&t=2475s

Wgl gośc pokazuje jak zmieniając mniej więcej od 3 do 6 linijek w drzewie sum uzyskać drzewo max-ów.

Lepszego omówienia na polskim YT raczej nie znajdziesz. Ja uczyłem się dzisiaj z tego, i napisałem sum i maxów(wydaje mi się, że mniej więcej kumam o co chodzi)
1
komentarz 21 marca 2023 przez polandonion Dyskutant (7,560 p.)
Oglądałem, tyle że za pierwszym, 2., 3. razem nie rozumiałem w ogóle tego drzewa. Wystarczyło usiąść przed kartką papieru, rozrysować sobie jakieś małe drzewko, z dużą ilością przykładów i w końcu załapałem. Teraz jakbym obejrzał, to bym wszystko zrozumiał, więc mój sposób na naukę to nauczyć się zamysłu/idei jakiejś strukturi danych, a implementacją wolę zająć się sam. Ale dzięki, że włączyłeś się do dyskusji :D

Podobne pytania

0 głosów
2 odpowiedzi 342 wizyt
0 głosów
2 odpowiedzi 465 wizyt
pytanie zadane 2 września 2020 w Rozwój zawodowy, nauka, praca przez Panareno Nowicjusz (120 p.)

93,102 zapytań

142,068 odpowiedzi

321,530 komentarzy

62,443 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...