Drzewa przedziałowe (projekt)

Wymagania i kryteria oceniania

Należy zaimplementować drzewo przedziałowe (ang. Segment Tree) w jednym z niżej wymienionych wariantów.

Ocena zależy od wybranego wariantu i może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Warianty

Drzewo punkt-przedział (na ocenę 3)

Należy zaimplementować drzewo przedziałowe, które pamięta ciąg n liczb (o indeksach 0, 1, …, n-1) i umożliwia wykonywanie następujących operacji:

• zmiana wartości i-tej liczby w czasie O(log(n));
• obliczenie sumy wszystkich liczb w podanym przedziale [p, k], tj. sumy liczb o indeksach p, p+1, …, k, w czasie O(log(n));
• skonstruowanie drzewa dla podanej tablicy n liczb w czasie O(n).

Drzewo przedział-punkt (na ocenę 3,5)

Należy zaimplementować drzewo przedziałowe, które reprezentuje ciąg n liczb (o indeksach 0, 1, …, n-1) i umożliwia wykonywanie następujących operacji:

• dodanie podanej wartości do wszystkich liczb w podanym przedziale [p, k], tj. do liczb o indeksach p, p+1, …, k, w czasie O(log(n));
• obliczenie wartości i-tej liczby w czasie O(log(n));
• skonstruowanie drzewa dla podanej tablicy n liczb w czasie O(n).

Drzewo przedział-przedział (na ocenę 4)

Należy zaimplementować drzewo przedziałowe, które reprezentuje ciąg n liczb (o indeksach 0, 1, …, n-1) i umożliwia wykonywanie następujących operacji:

• dodanie podanej wartości do wszystkich liczb w podanym przedziale [p, k], tj. do liczb o indeksach p, p+1, …, k, w czasie O(log(n));
• obliczenie sumy wszystkich liczb w podanym przedziale [p, k], tj. sumy liczb o indeksach p, p+1, …, k, w czasie O(log(n));
• skonstruowanie drzewa dla podanej tablicy n liczb w czasie O(n).

Zadanie z armatką (na ocenę 5)

Dana jest liczba celów wraz z ich odległościami od armatki. Każda odległość podana jest jako liczba sekund, które upłyną od wystrzelenia pocisku z armatki do osiągnięcia celu.

Poczynając od chwili 0, armatka wystrzeliwuje jeden pocisk co 2 sekundy, tj. wystrzeliwuje pociski w chwilach: 0, 2, 4, itd. Każdy pocisk trafia w jeden wybrany cel.

Należy obliczyć czas potrzebny na zestrzelenie wszystkich celów, tj. najwcześniejszą możliwą chwilę, w której pocisk osiągnie ostatni z nich. Ponadto chcemy móc szybko obliczać wynik po zmianie liczby celów znajdujących się w podanej odległości k (gdzie k < n) od armatki.

Celem jest więc zaimplementowanie struktury danych, która dla każdej odległości k z zakresu [0, n) przechowuje liczbę celów znajdujących się w odległości k od armatki i udostępnia następujące operacje:

• obliczanie czasu potrzebnego na zestrzelenie wszystkich celów w czasie O(log(n)),
• zmiana liczby celów w odległości k (dla dowolnego k < n) w czasie O(log(n)).

Skonstruowanie struktury (dla zadanej tablicy zawierającej liczby celów w odległościach 0, 1, …, n-1 od armatki) powinno mieć złożoność czasową O(n).

Przykład: Dla następujących celów:

Ostatni cel zostanie zestrzelony w chwili 9:

Po zmianie liczby celów w odległości 1 na 1:

Ostatni cel zostanie osiągnięty w chwili 8:

Po zmianie liczby celów w odległości 2 na 3:

Ostatni cel zostanie zestrzelony w chwili 13:

Przykładowe pytania sprawdzające

• Zilustrować działanie operacji zaimplementowanego drzewa.
• Jaka jest złożoność czasowa i pamięciowa poszczególnych operacji? Odpowiedź uzasadnij.
• Jaka jest złożoność pamięciowa zaimplementowanego drzewa? Odpowiedź uzasadnij.