Zadanie litery OI, Drzewa przedziałowe vs Drzewa licznikowe

Question

Robiac zadanie z OI-a: https://szkopul.edu.pl/problemset/problem/V1PYHlhJQGTY6KR5ODoTTYU4/site/?key=statement napisałem kod na 100pkt, drzewami przedziałowymi przedział - punkt, bardzo prosty 60linii. w książeczce OI pisze:

Do tego służyć może struktura danych zwana drzewem licznikowym lub przedziałowym2 . Jest to statyczne drzewo binarne zbudowane nad tablicą liczb t[1. .n]; pozwala ono na wykonywanie w czasie O(log n) następujących operacji:

ustaw(i, x) — przypisz t[i] := x;

suma(l, r) — zwróć sumę t[l] + t[l + 1] + . . . + t[r], przy czym l ¬ r.

1 - Drzewo licznikowe to to samo co drzewo przedziałowe przedział - punkt?

2 - Na Oi-a, polecacie jeszcze jakies struktury z przedzialami oprocz drzew przedział-punkt,punkt-przedział?

3 - Znacie jakies fajne zadania na drzewa przedziałowe?

Ps. Jak ktoś robi to zadanie, to polecam też popatrzeć na zadanie Kulki z finału 15 OIJ-a. Bardzo podobne.

Z góry dziękuję za odpowiedź i poświęcony czas!

edit: nwm czy dobrze przeczytalem, ale jesli to to ze trzyma sume wszystkich swoich potomkow w drzewie, to mozna drzewo podzielic dfs-em post order dodac na ciag i zrobic drzewo przedizał-punkt. Tylko nwm czy to jest drzewo licznikowe.

Answer 1

Drzewo licznikowe to tylko szczególna wersja drzewa przedziałowego punkt-przedział która zlicza sume na przedziale. Samo drzewo przedziałowe punkt-przedział może obliczać dowolną funkcję agregującą na przedziale np. max, xor itd.

Co ciekawe w g++ jest dostępna struktura bardzo podobna do drzewa licznikowego (link)

Na pewno trzeba jeszcze znać drewo przedział-przedział, dynamiczne drzewo przedziałowe, a także warto wiedzieć o drzewie Fenwicka

Comments

Jeżeli chodzi o jakieś zadanie to np. licznik długu z I etapu OI sprzed 2 lat

---

dzięki.