Na początek mała odskocznia od drzew przedział-przedział. Masz problem wyszukiwania maksimum w danym przedziale tablicy liczb. Przypomnij sobie dlaczego zwykłe drzewo przedziałowe jest szybsze od operowania na tablicy?
Odpowiedź jest prosta, w przypadku tablicy musimy sprawdzić każdą liczbę danego przedziału, a w przypadku drzewa szukamy minimalnego zbioru wierzchołków, który pokrywa ten przedział. Czyli, w większości przypadków, każdy sprawdzany wierzchołek będzie odpowiadał za więcej niż jedną liczbę.
Teraz wróćmy do aktualizacji przedziału. Dlaczego nie możemy użyć tablicy albo zwykłego drzewa przedziałowego?
Bo podobnie jak w przypadku powyżej musielibyśmy wykonać tyle aktualizacji ile jest liczb w przedziale.
Jak zatem sobie z tym poradzić?
Analogicznie jak w przypadku powyżej czyli zamiast aktualizować każdy element tablicy/liść drzewa osobno, zaktualizujmy tylko minimalny zbiór wierzchołków, który pokrywa ten przedział.
Oczywiście łatwo powiedzieć trudniej zakodować. Pierwszą rzeczą jaką musimy zrobić to wzbogacić nasze drzewo. Każdy jego wierzchołek powinien przechowywać dwie wartości:
- maxval[i] = maksymalną liczbę w przedziale za jaki odpowiada i-ty wierzchołek (tę wartość już przechowywałeś w t[i])
- val[i] = liczbę jaka została dodana do każdego elementu w przedziale za jaki odpowiada i-ty wierzchołek
Teraz przeróbmy funkcję aktualizującą przedział, tak żeby działała rekurencyjnie, podobnie do Twojej funkcji szukaj. Niech przyjmuje ona następujące parametry:
- [x, y) - przedział, na którym dokonywana jest aktualizacja, prawostronnie otwarty
- v - wartość jaką dodajemy na przedziale [x, y)
- i - wierzchołek drzewa, który aktualizujemy
- [l, r) - przedział za jaki odpowiada i-ty wierzchołek drzewa, prawostronnie otwarty
W funkcji sprawdzamy 3 przypadki:
- Jeżeli przedział [l, r) w żadnym stopniu nie pokrywa się z przedziałem [x, y) to kończymy wykonanie funkcji, bo nie musimy nic aktualizować.
- Jeżeli przedział [l, r) w całości zawiera się w przedziale [x, y) to zwiększamy wartość val[i] o v, ale nie kończymy działania funkcji. To właśnie w tej operacji jest największy zysk, bo zamiast wykonywać r-l aktualizacji robimy tylko 1.
- Jeżeli pierwsze 2 przypadki nie były spełnione tzn. że przedział [l, r) częściowo zawiera się w [x, y). Musimy zatem znaleźć pod-przedziały [l, r), które będą w pełni zawierały się w [x, y). W tym celu wywołujemy rekurencyjnie aktualizację dla wierzchołka 2i, który odpowiada za przedział [l, (l + r) / 2) i wierzchołka 2i + 1, który odpowiada za przedział [(l + r) / 2, r).
Po wykonaniu punktu 2 albo 3 musimy zaktualizować wartość maksymalną dla przedziału [l, r) czyli wartość maxval[i]. Tutaj mamy 2 przypadki:
- Jeżeli [l, r) jest przedziałem 1-elementowym czyli liściem drzewa to maxval[i] = val[i]
- Jeżeli [l, r) jest przedziałem większym niż 1-elementowy to maxval[i] będzie sumą val[i], czyli tych aktualizacji, które całkowicie pokryły przedział [l, r), oraz maksymalnej wartości jaką otrzymaliśmy dla częściowych aktualizacji [l, r) czyli dla jego pod-przedziałów. Tą drugą wartość możemy uzyskać od dzieci i-tego wierzchołka czyli z wierzchołków 2i oraz 2i + 1. Podsumowując maxval[i] = val[i] + max(maxval[2i], maxval[2i + 1]).
Po zmianach funkcja aktualizuj prezentuje się następująco:
void aktualizuj(int x, int y, int v, int i, int l, int r)
{
if (y <= l || r <= x) {
return;
}
if (x <= l && r <= y) {
val[i] += v;
} else {
int m = (l + r) / 2;
aktualizuj(x, y, v, i + i, l, m);
aktualizuj(x, y, v, i + i + 1, m, r);
}
if (l + 1 == r) {
maxval[i] = val[i];
} else {
maxval[i] = val[i] + max(maxval[i + i], maxval[i + i + 1]);
}
}
Teraz zajmijmy się funkcją szukaj, która ma nam znaleźć maksimum w przedziale [x, y). Podobnie jak w Twojej dotychczasowej wersji będzie ona rekurencyjna i będzie przyjmowała taki sam zestaw parametrów czyli:
- [x, y) - przedział, w którym wyszukujemy maksimum, prawostronnie otwarty
- i - wierzchołek drzewa, w którym wyszukujemy
- [l, r) - przedział za jaki odpowiada i-ty wierzchołek drzewa, prawostronnie otwarty
W tej funkcji również sprawdzamy 3 przypadki:
- Jeżeli przedział [l, r) w żadnym stopniu nie pokrywa się z przedziałem [x, y) to jako maksimum zwracamy wartość 0.
- Jeżeli przedział [l, r) w całości zawiera się w przedziale [x, y) to zwracamy maksimum [l, r) obliczone przy jego aktualizacji czyli maxval[i].
- Jeżeli pierwsze 2 przypadki nie były spełnione tzn. że przedział [l, r) częściowo zawiera się w [x, y). Musimy zatem znaleźć pod-przedziały [l, r), które w pełni zawierają się w [x, y) i z nich wyciągnąć maksymalne wartości. W tym celu wywołujemy rekurencyjnie wyszukiwanie dla wierzchołka 2i, który odpowiada za przedział [l, (l + r) / 2) i wierzchołka 2i + 1, który odpowiada za przedział [(l + r) / 2, r). Do większej z wartości zwróconych przez rekurencyjne wywołania musimy jeszcze dodać wartość aktualizacji na całym przedziale [l, r) czyli val[i]. Suma tych wartości będzie zwracanym maksimum. Podsumowując w tym przypadku zwracamy wartość val[i] + max(szukaj(x, y, 2i, l, (l + r) / 2), szukaj(x, y, 2i + 1, (l + r) / 2, r).
Po zmianach funkcja szukaj prezentuje się następująco:
int szukaj(int x, int y, int i, int l, int r)
{
if (y <= l || r <= x) {
return 0;
}
if (x <= l && r <= y) {
return maxval[i];
}
int m = (l + r) / 2;
int max1 = szukaj(x, y, i + i, l, m);
int max2 = szukaj(x, y, i + i + 1, m, r);
return val[i] + max(max1, max2);
}
I to by było na tyle, jeżeli masz jakieś pytania to pisz śmiało. Jeżeli chodzi o użycie tych funkcji to wartości x, y i v są zależne od zapytania. Pozostałe zawsze będą miały takie same wartości czyli i = 1, l = 1, r = n.