Wykład 2. Drzewa przedziałowe

Lista zagadnień, które zostały omówione:

  1. Operacje na krotkach. Chcemy zaprojektować strukturę danych do wykonywania prostych operacji na krotkach -- wektorach postaci (v1,...,vk), gdzie viliczbami całkowitymi z niedużego zakresu. Żądane operacje to: wstawianie i usuwanie krotek oraz zapytania o liczbę krotek, należących do danego k-wymiarowego prostopadłościanu [a1, b1] x ... x [ak, bk].
    Jak to zwykle bywa z zagadnieniami wielowymiarowymi, rozsądnym podejściem do rozwiązywania tego problemu jest rozpoczęcie od przypadku 1-wymiarowego, a następnie dodawanie kolejnych wymiarów.
    • Przypadek jednowymiarowy -- drzewo przedziałowe. W przypadku 1D przestajemy myśleć o krotkach, a zaczynamy myśleć o pojedynczych liczbach i zapytaniach o liczbę liczb z zadanego przedziału. Do rozpatrzenia tego przypadku posłużymy się statycznym drzewem, które dla ustalenia uwagi będziemy nazywać przedziałowym (nie jest mi znana żadna dużo lepsza terminologia, więc pozostanę przy tej nazwie). Załóżmy więc, że wszystkie elementy, jakie będziemy wstawiać i usuwać, pochodzą z ograniczonego przedziału [0,M-1], gdzie M=2k dla pewnego k całkowitego. Liście drzewa reprezentują teraz pojedyncze elementy, a węzły wewnętrzne -- pewne ich przedziały. Oto przykładowe takie drzewo zbudowane dla M=8:
      Drzewo przedzialowe
      Przedziały występujące w węzłach drzewa nazywać będziemy bazowymi. Widzimy, że głębokość takiego drzewa jest rzędu O(log(M)), a liczba węzłów -- O(M) (jest ich dokładnie 2k + 2k-1 + ... + 20 = 2k+1 - 1 = 2*M - 1). Poza tym drzewo takie możemy pamiętać w tablicy statycznej, w której węzły są ponumerowane poziomami, czyli korzeń drzewa ma numer 1, jego lewy syn -- 2, jego prawy syn -- 3 itd. (numeracja jak w kopcu). Jeżeli teraz rozważany węzeł ma numer v, to jego lewy syn ma numer 2*v, prawy -- 2*v+1, a jego ojciec -- v/2 (część całkowita oczywiście). To, wraz ze spostrzeżeniem, że liść [x, x] ma numer M+x, pozwala już na bardzo łatwe nawigowanie po drzewie, w szczególności na spacer od danego liścia do korzenia:
      int v = M + x;
      while (v != 1) {
         // Zrób coś.
         v /= 2;
      }

      Z każdym węzłem drzewa zwiążemy teraz pewną wartość w (czyli po prostu wzbogacimy to drzewo). Wartość ta dla liścia będzie po prostu zliczać wystąpienia elementu oznaczonego przez ten liść, natomiast dla węzła wewnętrznego -- wystąpienia wszystkich elementów z przedziału bazowego przezeń reprezentowanego. W szczególności dla v-wewnętrznego zachodzi w[v] = w[2*v] + w[2*v+1]. Kiedy wstawiamy dany element x do drzewa (usuwanie działa podobnie), to musimy zaktualizować wartości w we wszystkich przedziałach bazowych zawierających x. Na każdym poziomie drzewa jest co najwyżej jeden taki węzeł (bo przedziały bazowe na danym poziomie są parami rozłączne), no a wszystkie te przedziały układają się w ścieżkę od liścia [x, x] do korzenia. Oto przebieg wstawienia elementu 2 do przykładowego drzewa:
      Wstawianie do drzewa
      No to możemy już zapisać kod wstawiania do drzewa:

      void insert(int x, int val) { /* val==1 to wstawianie, val==-1 to usuwanie */
         int v = M + x;
         w[v] += val;
         while (v != 1) {
           v /= 2;
           w[v] = w[2 * v] + w[2 * v + 1];
         }
      }

      A jak teraz zrealizować zapytanie o przedział? Otóż trzeba umieć rozłożyć dany przedział na parami rozłączne przedziały bazowe; wtedy wynikiem zapytania będzie suma wartości w z tych przedziałów. Okazuje się, że można zawsze dokonać takiego rozkładu na O(log(M)) przedziałów bazowych i że złożoność czasowa tej operacji to także O(log(M)). Dla zapytania o przedział [a, b] startujemy mianowicie z liści [a, a] i [b, b] i idziemy od nich w górę ku korzeniowi, aż ścieżki się nie spotkają. Za każdym razem, jeżeli na lewej ścieżce (dla a) idziemy w górę tak, że jesteśmy lewym synem ojca, to do rozkładu bierzemy prawego brata; na prawej ścieżce postępujemy symetrycznie. Rozkład ten to zatem przedziały [a, a], [b, b] i takie "bombki", ale dyndające do wnętrza choinki (na rysunku oznaczone trójkątami):
      Rozklad na przedzialy bazowe
      Widać, że rozkład taki jest nieduży i że można go szybko policzyć; pytanie, czy jest on w ogóle taki, jak chcemy, czyli czy pokrywa cały przedział [a, b] i wybrane przedziały są parami rozłączne? Aby pokazać, że taki właśnie jest, wyobraźmy sobie ścieżkę z jakiegokolwiek liścia [x, x] do korzenia, gdzie a ≤ x ≤ b. Ścieżka ta musi wejść w pewnym momencie do punktu, gdzie spotykają się ścieżki biegnące z a oraz b (dlaczego?). Jeżeli wejdzie tam od lewej strony, to wejdzie tak, jak ścieżka biegnąca z [a, a], a w przeciwnym wypadku -- tak, jak ścieżka z [b, b]. Wniosek: ścieżka z [x, x] musi w pewnym momencie wejść na którąś z tych dwóch ścieżek, a moment wejścia na tę ścieżkę to albo prawa bombka na lewej ścieżce, albo lewa bombka na ścieżce prawej. Ponieważ ścieżka z [x, x] do korzenia reprezentuje zbiór wszystkich przedziałów bazowych, zawierających x, to pokazaliśmy właśnie, że x mieści się w którejś bombce i że w dokładnie jednej, czyli to, co trzeba. Oto przykład, jak wygląda zapytanie o przedział [1, 5] dla przykładowego drzewa:
      Zapytanie o przedzial
      A teraz pora na implementację operacji zapytania:

      int query(int a, int b) {
         int va = M + a, vb = M + b;
         /* Skrajne przedziały do rozkładu. */
         int wyn = w[va];
         if (va != vb) wyn += w[vb];
         /* Spacer aż do momentu spotkania. */
         while (va / 2 != vb / 2) {
           if (va % 2 == 0) wyn += w[va + 1]; /* prawa bombka na lewej ścieżce */
           if (vb % 2 == 1) wyn += w[vb - 1]; /* lewa bombka na prawej ścieżce */
           va /= 2; vb /= 2;
         }
         return wyn;
      }

      Zakończyliśmy analizę przypadku jednowymiarowego. Można by się spytać, po co opisywać to wszystko tak szczegółowo, skoro to wszystko jest w sumie proste. Otóż po to jest ten opis, że przedstawiona implementacja jest nierekurencyjna i przez to bardzo efektywna (a przy okazji bardzo krótka), a znane mi są przypadki, kiedy na jakimś konkursie był na tyle wyżyłowany limit czasowy, że rekurencyjnie zaimplementowane drzewo przedziałowe nie mieściło się w czasie, a iteracyjnie -- już tak.

    • Przypadek wielowymiarowy. A konkretniej to zaczniemy od dwóch wymiarów. Rozwiązaniem dla tego przypadku będzie... drzewo przedziałowe drzew przedziałowych. Pierwszy "poziom" drzewa jest skonstruowany dla pierwszych współrzędnych krotek i wygląda tak samo, jak zwykłe drzewo przedziałowe, tyle że w węzłach tego drzewa zamiast wartości są drzewa przedziałowe zbudowane po drugich współrzędnych krotek; te drzewa drugiego poziomu mają już w węzłach normalne wartości w, dokładnie tak jak w przypadku 1D. Oto przykładowe takie drzewo dla punktów z prostokąta [0, 1] x [0, 3]:
      Wielowymiarowe drzewo przedzialowe
      Aby wstawić krotkę do tego drzewa, przechodzimy ścieżką od liścia do korzenia odpowiadającą wartości pierwszej współrzędnej tej krotki, a następnie w każdym drzewie drugiego poziomu znajdującym się na tej ścieżce wykonujemy takie samo przejście, ale po ścieżce odpowiadającej wartości drugiej współrzędnej krotki. Dla przykładu, wstawienie krotki (0, 2) do przykładowego drzewa wykonywane jest następująco:
      Wstawianie do wielowymiarowego drzewa
      Widzimy, że koszt czasowy wstawiania krotek to O(log2(M)). Zapytanie o prostokąt [a, b] x [c, d] wykonywane jest analogicznie: najpierw przedział [a, b] rozkładamy na przedziały bazowe w drzewie pierwszego poziomu, a następnie w każdym z drzew drugiego poziomu odpowiadających węzłom z rozkładu wykonujemy standardowe (jednowymiarowe) zapytanie o przedział [c, d]. Wynikiem zapytania jest suma tego wszystkiego. Koszt czasowy zapytania to oczywiście także O(log2(M)). Wprawione oko Czytelnika zauważy zapewne, że rozwiązanie to świetnie się uogólnia na dowolną liczbę wymiarów; w d wymiarach struturą danych będzie drzewo drzew drzew drzew itd., a koszt czasowy operacji na nim wyniesie O(logd(M)).
    • Kwestia złożoności pamięciowej. Pozostaje jednak drobny problem, który dotychczas przemilczeliśmy -- jaka jest złożoność pamięciowa tej struktury? Tak jak w przypadku 1D mogliśmy sobie założyć, że punkty są z niedużego przedziału, tak w większej liczbie wymiarów, aby zmieścić się w limicie pamięciowym, trzeba by przedziały na współrzędne okroić już w znaczący sposób. Istnieją (co najmniej) trzy wyjścia z tej sytuacji, a każde ma swoje wady i zalety. Oto one:
      • Rozwiązanie całkowicie statyczne. Zakładamy znajomość wszystkich krotek, jakie pojawią się w trakcie przetwarzania (można to zastosować, jeżeli zadanie jest sformułowane "dynamicznie", ale my tak naprawdę i tak możemy na początek wczytać sobie wszystkie dane). W takim wypadku możemy wszystkie drzewa (zarówno to wyższego, jak i te niższego poziomu) zbudować od razu, gdyż znamy wszystkie liście, jakie mogą się w nich pojawić (czyli w tym wypadku liście drzewa nie będą numerowane kolejnymi liczbami 0, 1, ..., ale kolejnymi faktycznie możliwymi liczbami a1, a2, ...). Wady: to rozwiązanie trochę przykro się implementuje, bo trzeba te drzewa wziąć i zbudować, co jest minimalnie mniej przyjemne niż prosta deklaracja tablicy czy tablicy tablic, jak to było w poprzednim przypadku. No i oczywiście założenie o znajomości wszystkich krotek na wejściu nie jest przyjemne. Zaleta: rozwiązanie tak efektywne pamięciowo, jak tylko się da, a przy tym całkiem szybkie.
        Uwaga: prostym, ale całkiem przyjemnym usprawnieniem opisanego rozwiązania jest przeskalowanie wartości. Przy takim podejściu trzymamy sobie dodatkową mapę z liczb a1, a2, ... w liczby 0, 1, ... i węzły drzewa opisujemy (i konstruujemy) jak poprzednio, a jedynie przed kolejnymi zapytaniami i wstawieniami przechodzimy między wartościami faktycznymi a przeskalowanymi. Dla każdej instancji drzewa (czy to wyższego, czy niższego poziomu) musimy mieć osobną taką mapę oczywiście.
      • Dynamicznie rozwijane statyczne drzewo. W tym rozwiązaniu nie zakładamy już znajomości wszystkich krotek na wstępie, a jedynie znajomość przedziału ograniczającego wielkości współrzędnych. Drzewo będzie zatem poniekąd statyczne, ale... dynamicznie rozwijane! Otóż zaczynamy sobie od takiego "skompresowanego" drzewa, jak to na poniższym rysunku (struktura skonstruowana podobnie jak poprzednio dla prostokąta [0, 1] x [0, 3]):
        Puste dynamiczne drzewo
        Tutaj drzewo ma tylko jeden węzeł -- korzeń, a z nim związane drzewo niższego poziomu jest również skompresowane do korzenia. Jeżeli teraz chcemy coś wstawić, np. krotkę (1, 1), to rozwijamy drzewo wyższego poziomu tak, żeby istniała ścieżka od korzenia do liścia odpowiadającego przedziałowi [1, 1] (a żeby na tej ścieżce każdy węzeł posiadał oboje dzieci, choć jedno z nich potencjalnie dalej skompresowane), a następnie we wszystkich węzłach na tej ścieżce to samo rozwinięcie wykonujemy w drzewach niższego poziomu:
        Dynamiczne drzewo po jednym wstawieniu
        Kolejne wstawienia powodują coraz większe rozwijanie drzewa; tak wygląda nasze drzewo po wstawieniu kolejnej krotki -- (0, 2):
        Dynamiczne drzewo po drugim wstawieniu
        Koszty czasowe poszczególnych operacji nie zmieniły się, natomiast wielkość całej struktury po p wstawieniach krotek wyraża się jako O(p*logd(M)), gdzie d to wymiar przestrzeni krotek. Zasadniczą wadą tego podejścia jest to, że drzewo musimy pamiętać z użyciem wskaźników (można tego także uniknąć: tworząc nowy węzeł, umieszczamy go na końcu globalnego "stosu" węzłów, implementowanego za pomocą ogromnej tablicy). Kolejna wada jest taka, że operacje na takim drzewie musimy już jednak implementować rekurencyjnie, przez co tracimy nieco na efektywności. Z kolei zaletą tej metody jest przede wszystkim brak potrzeby znajomości wszystkich krotek na wstępie; pozwala to między innymi uniknąć potrzeby przykrej implementacji tworzenia drzewa.
      • Hashmapa, czyli udajemy, że nie ma problemu. Ostatnie z rozwiązań jest tak naprawdę zakamuflowaną implementacją poprzedniego. Zakładamy w nim, że np. M=230 i całkiem wprost powielamy implementacje operacji wstawiania i zapytania z podstawowego, statycznego rozwiązania, ale zastępujemy tablicę w mapą albo hashmapą w. W ten sposób jedynie pola, do których się odwołamy, będą się w hashmapie znajdować, co odpowiada niejawnemu dynamicznemu rozwijaniu drzewa. Zalety takiego podejścia są jasne: implementacja pozostaje praktycznie niezmieniona w stosunku do najprostszej wersji; uzyskujemy podobne parametry jak w rozwiązaniu poprzednim, ale nie musimy używać jakichkolwiek wskaźników czy rekursji. Podejście to nie jest jednak pozbawione wad. Główną z nich wydaje się być dodatkowy narzut czasowy wynikający z użycia mapy albo hashmapy (poza tym to rozwiązanie działa praktycznie równie efektywnie jak poprzednie). Drugą, trochę ukrytą wadą jest właśnie konieczność użycia hashmapy: jeżeli Czytelnik nigdy tego w C++ nie robił, a sądzi, że umie, to szczerze zachęcam do spróbowania swoich sił i napisania kompilującego się i działającego kodu, który wykonuje chociażby proste operacje na hashmapie.
      • Wniosek: Są trzy możliwe podejścia do opisanego problemu, który dotyczy zarówno przypadku wielowymiarowego, jak i jednowymiarowego z dużą wartością parametru M. Każde podejście ma swoje wady i zalety, więc wybór właściwej w danym kontekście implementacji opisanej struktury zależy wyłącznie od zapotrzebowań.
  2. Inne proste warianty. Dotychczas całą uwagę w przypadku jednowymiarowym poświęciliśmy sytuacji, w której do struktury wstawiamy pojedyncze elementy (punkty), a pytamy o liczby punktów przedziałach. Ten wariant można przede wszystkim wzbogacić o to, żeby wstawianym punktom przypisać pewne wartości, a następnie sparametryzować go operacją, jaka ma być wykonywana przy zapytaniach. Interesować nas mogą przede wszystkim operacje + (suma wartości elementów przedziału) i max. Widać, że takie wzbogacenie można wykonać natychmiastowo -- wystarczy zmienić znaczenie wartości w i obliczać je w sposób z tym zgodny.
    Można także rozważyć wariant, w którym wstawiamy do struktury przedziały z przypisanymi wartościami, a pytamy się o sumę albo maksimum z wartości przedziałów zawierających dany punkt. Rozwiązanie tego wariantu osiągamy, zamieniając ze sobą implementacje operacji insert i query i to właściwie tyle.
  3. Wariant "przedział-przedział". Tym razem parametrem zarówno wstawienia, jak i zapytania będzie przedział; okazuje się, że ten wariant jest istotnie trudniejszy od poprzedniego. Dlaczego? Otóż gdybyśmy po prostu próbowali w operacjach wstawienia i usunięcia rozkładać przedziały na bazowe, to i tak nie byłoby pewności, że w przypadku przecinających się niepusto przedziałów miałyby one w rozkładzie choć jeden wspólny przedział bazowy.
    Rozwiązanie sformułujemy dosyć ogólnie: problem sparametryzujemy tym, jaka operacja jest wykonywana przy wstawianiu, a jaka przy zapytaniu. Jednoznaczną charakteryzacją wariantu będzie po prostu para, np. (+, max). Pierwsza współrzędna oznacza to, jaka operacja jest wykonywana przy wstawieniu:
    • + oznacza, że wszystkim elementom z przedziału [a, b] ich aktualną wartość powiększamy o daą stałą c,
    • max oznacza, że dla każdego elementu x z przedziału [a, b] wykonujemy operację w[x] = max(w[x], c).

    Druga współrzędna wskazuje operację, jaką należy wykonać na wartościach punktów z przedziału [a, b], żeby obliczyć wynik zapytania: będzie to albo suma (+), albo maksimum (max) z tych wartości. Ta parametryzacja okazuje się całkiem praktyczna: rozwiązanie problemu (+, max) pozwala rozwiązać zadanie Koleje z I etapu IX Olimpiady Informatycznej, a problemu (max, max) -- zadanie Tetris 2D, czyli dwuwymiarową wersję zadania Tetris 3D z I etapu XIII Olimpiady Informatycznej (obszerniejszy opis rozwiązań obu wersji zadania można znaleźć w Niebieskiej książeczce XIII OI).
    Rozwiązanie dla omawianego pakietu wariantów problemu jest możliwe dzięki wzbogaceniu drzewa przedziałowego o dwie wartości: w oraz W. Aby to dokładnie zrozumieć, sposób wzbogacenia opiszemy dla przypadku (+, max), a potem przeniesiemy na pozostałe. Wartość w dla węzła v będzie oznaczać łączny wkład wszystkich wstawionych już przedziałów do przedziału bazowego odpowiadającego v, czyli sumę wartości wszystkich przedziałów, w których rozkładach występuje ten przedział bazowy związany z v. Wartość W zdefiniujemy tak, żeby:

    • w przypadku zapytania o wynik dla przedziału bazowego [a, b] odpowiadającego węzłowi v drzewa, odpowiedź będzie zależała tylko od wartości w na ścieżce od korzenia od v oraz od wartości W dla węzła v,
    • dało się ją wyliczać rekurencyjnie, czyli na podstawie wartości W dzieci węzła.

    Przyjrzyjmy się pierwszemu z powyższych podpunktów. W naszym przypadku wartości w dla węzłów na ścieżce do v odpowiadają wkładom ze wszystkich wstawionych przedziałów, które w całości zawierały [a, b], a zatem te wkłady musimy tak czy siak dodać do ogólnego wyniku zapytania (takie przeskalowanie-przesunięcie wyniku). Wartość W będzie odpowiadała ścieżce od v do pewnego liścia z poddrzewa ukorzenionego w v, dla której suma wartości w napotykanych węzłów jest największa możliwa. Tak zdefiniowane W będzie po prostu oznaczać maksimum z wartości elementów przedziału [a, b], pomniejszonych o wkład z już wstawionych przedziałów, które w całości zawierały [a, b]. Łatwo dalej zauważyć, że wartość tę jesteśmy w stanie wyznaczać rekurencyjnie, bo ona właśnie działa jak długość najdłuższej ścieżki z węzła w dół.
    Jesteśmy już gotowi do zapisania żądanych relacji, opisanych w powyższych dwóch podpunktach:

    • 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].

    Pozostaje nam teraz zastanowić się, dlaczego te dwie relacje już wystarczają do zapisania wstawiania przedziałów i zapytań o przedział. Oto pseudokody tych operacji; wstawianie:

    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;
    }

    zapytanie:

    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;
    }

    Przy implementacji zapytania wykorzystaliśmy fakt, że wynik zapytania o przedział niebazowy wyraża się bezpośrednio przez wyniki zapytań o przedziały bazowe występujące w jego rozkładzie. Operacje są zapisane w pseudokodzie tak, że każdą z nich można już doprecyzować z użyciem albo iteracyjnego, albo rekurencyjnego algorytmu rozkładania przedziału na przedziały bazowe.
    Podane schematy wstawiania i zapytań są uniwersalne; jedyne, czego im trzeba, to istnienia dwóch wzorów, takich jak opisane powyżej. Zastanówmy się na przykład, jak wyglądałyby takie wzory dla problemu Tetris 2D, czyli (max, max). Parametr w oznaczać będzie ponownie sumaryczny wkład wszystkich przedziałów, które w rozkładzie na przedziały bazowe zawierają dany węzeł, tyle że tym razem sumaryczny wkład oznaczałby maksimum z ich wartości, a nie sumę. Parametr W będzie w tym przypadku oznaczał po prostu maksimum z wartości w w całym poddrzewie odpowiadającym danemu węzłowi. Taka charakteryzacja pozwala już całkiem łatwo zapisać żądane zależności:

    • wynik([a,b]) = max(w[v/2], w[v/4], ..., w[root], W[v]),
    • W[v] = max(w[v], W[2*v], W[2*v + 1]), a dla liści W[v] = w[v].

    Podobne zależności, ale tym razem zależne jeszcze od głębokości rozważanych węzłów w drzewie, można zapisać także dla przypadku (+, +); pozostawiamy je Czytelnikowi jako ćwiczenie. No dobrze, dla niecierpliwych rozwiązanie jest tutaj.
    Jest w sumie jeszcze jedna kombinacja, o której jeszcze w ogóle nie wspomnieliśmy, tzn. (max, +). Okazuje się jednak, że w tym przypadku opisany algorytm zupełnie nie działa i najprawdopodobniej nie da się dla niego znaleźć żadnego dobrego sposobu zdefiniowania parametrów w i W... No cóż, smutne, ale jest to wyjątek w budowanej teorii.
    Jako ciekawostkę na zakończenie prezentujemy kod w C++ implementujący operacje na drzewach przedziałowych typu przedział-przedział, sparametryzowany operacjami, jakie zamierzamy wykonywać ((+, +) lub (+, max), lub (max, max)), wraz z przykładem zastosowania do rozwiązania wspomnianego zadania Koleje z IX OI. Kod ten jest niestety dosyć zagmatwany właśnie ze względu na tę ogólność, a także ze względu na sztywne założenie o unikaniu rekursji w implementacji funkcji, niemniej jednak kilka jego elementów może być całkiem pouczających, więc zachęcamy do lektury.
    Jeżeli komuś jeszcze mało możliwych operacji na drzewie, to mamy na zakończenie jeszcze jedną, o której wręcz wstyd zapomnieć: przypisanie. Można z jego pomocą utworzyć pary (=, max) oraz (=, +), w których działa ono po prostu bardziej "bezwzględnie" niż operacja max. Niestety uwzględnienie tej operacji wymaga dość znacznej modyfikacji naszej struktury; w szczególności, w tym przypadku o wiele łatwiejsze okazują się implementacje rekurencyjne niż iteracyjne operacji na drzewie. Nie zrazimy się tak do końca tymi trudnościami i w kilku słowach omówimy, jak sobie z tym przypadkiem poradzić.
    Oprócz wartości w oraz W, w każdym węźle drzewa będziemy przechowywać bit aktualności. Jego znaczenie będzie następujące: jeżeli węzeł v ma ustawiony bit aktualności oraz żaden jego przodek nie ma, to v przechowuje w parametrze w najbardziej aktualną wartość przypisaną wszystkim elementom przedziału bazowego, który v reprezentuje. Intuicja stojąca za tym wszystkim jest następująca: w momencie wykonywania operacji insert([a, b], c) tak naprawdę powinniśmy we wszystkich węzłach drzewa reprezentujących przedziały bazowe zawarte w [a, b] ustawić wartość w na c, ale że nie mamy na to czasu, to ustawimy tę wartość tylko w niektórych takich węzłach -- dokładnie tych z rozkładu przedziału [a, b] na przedziały bazowe -- i im ustawimy bit aktualności. Kiedy przy jakiejś dalszej operacji na strukturze jednak zajdzie potrzeba zejścia głębiej niż do tych przedziałów, to na bieżąco będziemy "spychać" aktualną wartość w dół, ale znów jedynie na tyle, na ile zajdzie potrzeba.
    Dla ustalenia uwagi, w dalszej części będziemy analizować przypadek (=, max), troszeczkę łatwiejszy niż (=, +). Wspólną podprocedurą operacji wstawiania i zapytania będzie procedura przepchnięcia, która dba o to, żeby wartości w na ścieżkach od korzenia do liści odpowiadających a oraz b były jak najbardziej aktualne. Przepchnięcie startuje więc od korzenia i wędruje w dół po tych ścieżkach, aż natrafi na wierzchołek z ustawionym bitem aktualności. Kiedy to nastąpi, bit napotkanego wierzchołka zostaje wyzerowany, a wartość zostaje przekazana obydwu dzieciom i teraz one uzyskują bit aktualności.

    void przepchnij([a, b], v) {
       interval [x, y] = v.przedzial;
       if ([x, y] zawarty w [a, b] || [x, y] rozlaczny z [a, b])
         /* To pokrywa także przypadek v będącego liściem. */
         return;
       if (v.aktualny) {
         v.lewy.w = v.w; v.lewy.aktualny = true;
         v.prawy.w = v.w; v.prawy.aktualny = true;
         v.aktualny = false;
       }
       przepchnij([a, b], v.lewy);
       przepchnij([a, b], v.prawy);
    }

    Po wykonaniu przepchnięcia operacje wstawienia i zapytania są już całkiem proste. Przy wstawianiu, które w tym wypadku jest tak naprawdę przypisywaniem, rozkładamy przedział [a, b] na bazowe, w nich wpisujemy jako wartość w parametr wstawiania c i ustawiamy bity aktualności, po czym we wszystkich tych wierzchołkach oraz na obydwu ścieżkach modyfikujemy wartości parametru W za pomocą tego samego wzoru, co poprzednio dla maksimum (W[v] = max(w[v], W[2*v], W[2*v + 1])). w[v] dla wierzchołka nieaktualnego traktujemy przy tym jako minus nieskończoność. Wynik zapytania, podobnie jak poprzednio, wyznaczamy na podstawie wyników dla przedziałów z rozkładu [a, b] na bazowe, a dla bazowych -- ze wzoru identycznego jak poprzednio w przypadku (max, max): wynik = max(w[v/2], w[v/4], ..., w[root], W[v]); uwaga o wartościach w[v] dla v-nieaktualnych pozostaje w mocy.
    Na tym kończymy już opis funkcjonalności typu przedział-przedział drzew przedziałowych, a dokładniejszy opis operacji dla przypadków (=, *) dla * = max, + pozostawiamy Czytelnikowi jako ćwiczenie.

  4. Co ciekawego można wsadzić do drzewa przedziałowego? Dotychczas w węzłach drzew przedziałowych przechowywaliśmy wyłącznie liczby całkowite (czasem jedną, czasem dwie); teraz pokażemy kilka przykładów, w których węzły mogą przechowywać coś ciekawszego niż liczby. Pierwszy przykład takiego zastosowania daje zadanie Pole uprawne z Potyczek Algorytmicznych 2006; jeżeli Czytelnik zadania nie zna albo nie pamięta, to zachęcamy do przeczytania go teraz.
    Każdy pasek z pola możemy reprezentować jako przedział [xi, yi] pól dopuszczalnych. Będziemy analizowali kolejne wiersze planszy i próbowali w nich umieszczać górny rząd pól prostokąta c x d; aby sprawdzić, czy (i na ile sposobów) nasz prostokąt się w tych wierszach zmieści, analizujemy przecięcie przedziałów [xi, yi] ∩ ... ∩ [xi+c-1, yi+c-1]. Jeżeli ma ono długość l ≥ d, to nasz prostokąt można ułożyć w rozważanych wierszach na l-d+1 sposobów, a w przeciwnym przypadku -- na 0 sposobów. Ale jak tu można wykorzystać drzewo przedziałowe? Otóż w liściach drzewa będziemy utrzymywać przedziały postaci [xi, yi], a w węzłach wewnętrznych -- przecięcia przedziałów z ich bezpośrednich dzieci, czyli innymi słowy przecięcia przedziałów z wszystkich liści w poddrzewach tych węzłów. Aby wyznaczyć wartość: [xi, yi] ∩ ... ∩ [xi+c-1, yi+c-1] dla danego indeksu i, wystarczy wtedy obliczyć przecięcie przedziałów przechowywanych w węzłach drzewa, które odpowiadają rozkładowi przedziału [i, i+c-1] na bazowe.
    Aby dobrze zrozumieć to, co przed chwilą zrobiliśmy, spróbujmy to uogólnić. Mamy dany ciąg elementów x0, ..., xn-1 i pewne działanie łączne na nich określone. Aby umieć odpowiadać na zapytania o wartość xi ⊕ ... ⊕ xj, czyli wynik działania operacji dla spójnego fragmentu wyjściowego ciągu określonego przez przedział indeksów [i, j], tworzymy drzewo przedziałowe, w którego liściach umieszczamy właśnie elementy xi, a w węzłach wewnętrznych -- wyniki operacji dla fragmentów ciągu im odpowiadających. Odpowiedź na żądane zapytanie otrzymujemy, rozkładając przedział [i, j] z zapytania na bazowe i licząc wynik operacji na wartościach z węzłów z rozkładu. W przypadku Pola uprawnego elementy xi były przedziałami, a ⊕ = ∩.
    Po tak ogólnej charakteryzacji problemu, z dalszymi przykładami nie będziemy już mieli większych problemów. Rozważmy na przykład zadanie Skrętka Liliany z ONTAK-a 2005. Tym razem elementami xi będą permutacje (przeploty) kabelków na kolejnych metrach skrętki, a działaniem -- składanie permutacji. Zapytania obsługujemy w tym przypadku tak samo jak w ogólnym schemacie, ale pojawia się też nowa operacja -- modyfikacji elementu. Możemy ją jednak wykonać tak samo, jak standardowe wstawienie elementu do drzewa, czyli aktualizując wartości na ścieżce od liścia odpowiadającego danemu elementowi do korzenia. Przedziały w węzłach, permutacje w węzłach... co będzie następne? Następne będą Autostrady z Potyczek Algorytmicznych 2005. W zadaniu musimy zliczać ścieżki w grafie skierowanym, więc już pierwsza intuicja podpowiada, że tym razem elementami xi będą macierze! Dokładniej, xi będzie macierzą sąsiedztwa między miastami województw i-tym a (i+1)-szym, a operacja będzie mnożeniem macierzy, co odpowiada zliczaniu ścieżek między niesąsiednimi województwami. Taka reprezentacja problemu pozwala już łatwo wyrazić operacje q i u z zadania odpowiednio przez zapytanie do drzewa przedziałowego i wstawienie do drzewa zmodyfikowanego elementu.
    Podsumowując, udało nam się drzewa przedziałowe wykorzystać do rozwiązaywania problemów, wyrażonych rozmaitymi obiektami -- przedziałami, permutacjami, macierzami -- a sukces osiągnęliśmy dzięki łączności działania na tych elementach; co ciekawe, działanie to nie w każdym przypadku było przemienne, ale to w tym przypadku w ogóle nie przeszkadza!

Wszelkie uwagi odnośnie tego wykładu, w tym niniejszego jego opisu, w tym wszelkie poprawki błędów, jakich niewątpliwie jest w nim mnóstwo, prosimy kierować do Jakuba Radoszewskiego.