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

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