Modyfikacja drzewa przedział-przedział

Question

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

Comments

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.

---

dzięki wielkie :D, jutro to zaimplementuje i dam znać czy się udało

---

@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)

---

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).

---

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

---

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) << ' ';
		}
	}
}

 

---

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

---

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) << ' ';
		}
	}
}

 

---

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

---

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

---

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

---

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

Answer 1

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)

Comments

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