Z tego linku http://www.mimuw.edu.pl/~cygan/wyklady/wyklad2.html próbuje zaimplementować wstawianie do przedziału i wyciąganie z niego maksa. Robię tak jak tam opisane i coś nie do końca mi to wychodzi dlatego chcę rozwiązać kilka nieścisłości. Chodzi mi o ten fragment.
* wynik([a,b]) = w[v/2] + w[v/4] + ... + w[root] + W[v], gdzie dzielenie przez dwa jest całkowitoliczbowe i odpowiada przejściu do ojca węzła w drzewie,
* W[v] = w[v] + max(W[2*v], W[2*v + 1]); oczywiście dla liści W[v] = w[v].
void insert([a, b], c) {
rozłóż przedział [a, b] na przedziały bazowe (robimy to jak poprzednio);
powiększ wartość w dla wszystkich tych przedziałów bazowych o c;
zaktualizuj wartości W dla wszystkich napotkanych po drodze węzłów:
bazowych i na ścieżkach do korzenia
za pomocą zależności rekurencyjnej na W;
}
int query([a, b]) {
rozłóż przedział [a, b] na przedziały bazowe;
policz wynik dla każdego z tych przedziałów za pomocą równości na wynik
uwaga: oczywiście sum wartości w na ścieżkach do korzenia nie liczymy
za każdym razem od zera, tylko je spamiętujemy po drodze;
return maksimum z tych wyników częściowych;
}
W insercie dla przedziału [1, 5] w aktualizuje dla czerwonych kółek ? A W duże dla niebieskich ?
W query dla tego samego przedziału wynik liczę dla scieżek tylko dla czerwonych ?
A dla przedziału [1,3]
W insercie w aktualizuje dla zielonych kółek ? A W duże dla fioletowych ?
W query dla tego samego przedziału wynik liczę dla scieżek tylko dla zielonych ?
Tu jest właśnie mój kod dla zadania "koleje" gdzie jest to drzewo http://wklej.org/id/31956/ u mnie w-moc W-smoc
