Wykład 2. Zastosowania drzew przedziałowych

 Zagadnienia poruszone na wykładzie:

  • Drzewo przedziałowe: właściwości oraz prosta i efektywna, nierekurencyjna implementacja.
  • Zastosowanie do problemu: "wstawianie punktów, zapytania o przedziały". Kilka uogólnień na przypadki wielowymiarowe.
  • Rozwiązanie problemu: "wstawianie przedziałów, zapytania o punkty".
  • Problem "wstawianie przedziałów, zapytania o przedziały". Rozważaliśmy wersje: (+, max) (zadanie Koleje z I etapu IX OI), (max, max) (zadanie "Tetris 2D") oraz (+, +) i znaleźliśmy dla nich wspólny mianownik. Wspomniane zostały także wersje (=, +) oraz (=, max) z rozwiązaniem za pomocą bitów aktualności.
  • Parę słów o tym, że w węzłach drzewa może być coś ciekawszego niż pojedyncze liczby (przedziały -- zadanie Pole uprawne z PA 2006; permutacje -- zadanie Skrętka Liliany z ONTAK-a 2005; macierze -- zadanie Autostrady z PA 2005).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 03.03.2008, 16:15-17:45.

Dostępne materiały: Nagrania, Notatki.