Segment trees

La oss si at du har en liste a med n tall, og du gjentatte ganger vil bli stilt spørsmålet “hva er summen av tallene fra og med indeks a til, men ikke med, indeks b?”. (Vi bruker “til, men ikke med” fordi det er mer behagelig å regne med enn “til og med”, men prinsippene blir de samme som om det hadde vært “til og med”.) Dersom ba alltid er det samme, kan man bruke en sliding window-algoritme til å forhåndsberegne alle svarene på O(n) tid og deretter svare på q spørsmål på konstant tid per spørsmål, altså total kjøretid O(n + q) – men dette er vanligvis ikke tilfelle. Likevel kan man bruke forhåndsberegning til sin fordel, ved å observere at summen av tallene fra og med a til, men ikke med, b (la oss kalle dette f(a, b)) – er lik f(0, b) – f(0, a). En slik sum av tallene fra 0 og utover kalles for en prefikssum. Dersom vi har alle de n prefikssummene fra og med f(0, 1) til og med f(0, n), kan vi svare på spørsmål i konstant tid per spørsmål. Utregningen av prefikssummene går på lineær tid siden f(0, i) = f(0, i – 1) + a[i - 1]. Dermed får vi igjen en kjøretid på O(n + q).

Dette er jo strålende, men noen ganger arbeider man med dynamiske data: innholdet i listen kan endre seg over tid. Ofte formulerer man slike problemer ved at man starter med en liste med n nuller, og så kommer den en sekvens av operasjoner, hvor hver operasjon enten er en oppdatering (update) eller et spørsmål (query). Totalt vil det komme u oppdateringer og q spørsmål, men hvilken rekkefølge de kommer i er ikke kjent. Slike oppgaver er som regel online, dvs. at for hvert spørsmål som kommer inn, må man svare på det med en gang; man kan ikke lese hele sekvensen med operasjoner først og så svare på alle spørsmålene etterpå. I en slik situasjon kan man jo fortsatt bruke prefikssum-trikset, men da vil hver oppdatering av et tall føre til at man må oppdatere opptil n av prefikssummene (i verste fall er det det første tallet som endres, og da må alle prefikssummene oppdateres) – kjøretiden blir da O(un + q), som er ugunstig hvis det er mange oppdateringer i forhold til spørsmål, men helt fint dersom man vet at det er mange spørsmål i forhold til spørsmål. Dersom man vet at det i stedet er mange oppdateringer i forhold til spørsnål, kan man like godt droppe alle fancy algoritmer, bare vedlikeholde et vanlig array og kjøre en vanlig summering for hvert spørsmål; kjøretiden blir da O(u + qn).

Ofte vet man ikke om det er flest oppdateringer eller spørsmål, evt. vet man at det er omtrent like mange av dem, og da er begge kjøretidene over ganske dårlige. Heldigvis kan vi gjøre det bedre ved å vri litt på prefikssumtrikset: kan vi strukturere summene på en annen måte, slik at hver oppdatering ikke påvirker like mange av de forhåndsberegnede summene? Dette kan vi gjøre på følgende måte:

  1. Dersom lengden av listen ikke er en toerpotens, er det greiest å utvide den til å bli en toerpotens (prøv å finne en bit shifting-basert algoritme får å runde et tall opp til nærmeste toerpotens) og bare fylle på med nuller i de ekstra posisjonene.
  2. Summer alle etterfølgende par av tall: a[0] + a[1], a[2] + a[3], a[4] + a[5] osv. (dvs. f(0, 2), f(2, 4), f(4, 6))
  3. Summer alle etterfølgende par av disse parsummene igjen, slik at man får f(0, 4), f(4, 8) osv.
  4. Summer alle etterfølgende par av disse kvadruppelsummene igjen, slik at man får f(0, 8), f(8, 16) osv.
  5. Fortsett til man når “toppen” og har summen av alle tallene, altså f(0, n).

Vi kan illustrere de forskjellige summene på denne måten:

              78
           /       \
       35             43
     /   \           /   \
  21      14      22      21
  / \     / \     / \     / \
11  10   2  12   8  14  15   6
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 0 2 4 8 5 3 7 7 7 8 2 4

Hver node representerer altså summen av tallene fra en del av listen, og fra-og-med- og til-men-ikke-med-indeksene kan gjerne lagres på hver node slik at de senere beregningene blir enklere:

                                            0-16
                                  /                       \
                     0-8                                             8-16
                /           \                                   /            \
         0-4                     4-8                     8-12                    12-16
     /         \             /         \             /         \              /         \
   0-2         2-4         4-6         6-8         8-10       10-12        12-14       14-16
  /   \       /   \       /   \       /   \       /   \        /   \       /   \       /   \
0-1   1-2   2-3   3-4   4-5   5-6   6-7   7-8   8-9   9-10  10-11 11-12 12-13 13-14 14-15 15-16

Man kan velge å lagre tallene i en faktisk trestruktur, men det er også mulig å bruke ett array per nivå i treet, eller til og med å legge alle elementene i samme array: da bør man la indeks 0 være ubrukt, legge roten i indeks 1, legge de to nodene på nest øverste nivå i indeks 2 og 3, osv.: 0 78 35 43 21 14 22 21 11 10 2 12 8 14 15 6 4 7 9 1 0 2 4 8 5 3 7 7 7 8 2 4. Gitt en node på indeks i vil barnenodene dens befinne seg på indeksene 2i og 2i + 1, og foreldrenoden vil befinne seg på indeks floor(i / 2).

Dersom n er en toerpotens, inneholder treet 2n – 1 elementer; treet har høyde lg n, og det tar linær tid å konstruere treet. Dersom vi nå får en oppdatering, tar det logaritmisk tid å oppdatere alle delsummene som inneholder det aktuelle elementet. Hvis f.eks. elementet på indeks 5 i den opprinnelige listen skal settes til 5, kan dette gjøres ved å øke alle delsummene som er markert her med 3 (siden tallet opprinnelig var 2):

               *
           /       \
        *             43
     /   \           /   \
  21       *      22      21
  / \     / \     / \     / \
11  10   *  12   8  14  15   6
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 0 * 4 8 5 3 7 7 7 8 2 4

Det vil si at det tar lg n tid å behandle en oppdatering. Men hvordan kan vi behandle et spørsmål om summen av elementene fra og med indeks a til, men ikke med, indeks b? Nå bør vi prøve å utnytte trestrukturen best mulig, ved å finne frem til de “bredeste” nodene som dekker over deler av det området vi er ute etter (uten å dekke over tall som er utenfor området). Hver node i treet vil representere en delsum som enten:

  • Bare inneholder elementer fra området det spørres om
  • Delvis inneholder elementer fra området det spørres om
  • Ikke inneholder noen elementer fra området det spørres om

La oss kalle disse nodetypene for B, D og I. Ved å traversere treet med et dybde først-søk får man undersøkt nodene fra toppen og nedover, kan man kategorisere nodene ut fra området de dekker over. For hver node må dybde først-søket returnere summen av den delen av det aktuelle listesegmentet som den noden bidrar med. Heldigvis trenger man bare å se på noen få av nodene:

  • Noder av type B er veldig bra, for der kan man bare bruke tallet i den noden direkte uten å se på noen av barna dens, for vi vet at vi er interessert i alle tallene som noden dekker.
  • Noder av type I er også bra, for der vet vi at vi ikke er interessert i noen av nodene som ligger lenger ned, så denne noden bidrar med summen 0.
  • Noder av type D er ikke nyttige i seg selv, så man må gå videre ned og se på barna dens, og denne noden bidrar med summen av barnas summer.

Når man implementerer dette dybde først-søket skikkelig, vil søket bare være innom noen få av nodene. Nedenfor har vi markert med nodetype-bokstaven de nodene man vil støte på dersom man spør om summen fra og med indeks 5 til, men ikke med, indeks 12:

               D
           /       \
        D              D
     /   \           /   \
   I       D       B       I
  / \     / \     / \     / \
11  10   D   B   8  14  15   6
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 I B 4 8 5 3 7 7 7 8 2 4

Antall noder man trenger å se på per spørsmål vil være proporsjonalt med høyden til treet, altså lg n. Altså kan vi behandle u oppdateringer og q spørsmål på O((u + q) lg n), som er vesentlig mye bedre. Denne datastrukturen kalles et segment tree. Merk at den også fungerer for å finne f.eks. største eller minste tall, eller i det hele tatt en hvilken som helst funksjon av en liste som er slik at f(AB) = f(A) op f(B) (der AB betyr en liste som består av dellistene A og B, og hvor op er en eller annen matematisk operasjon). Her er treet man ville ha fått hvis man var ute etter det minste tallet:

               0
           /       \
       0               2
     /   \           /   \
   1       0       3       2
  / \     / \     / \     / \
 4   1   0   4   3   7   7   2
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 0 2 4 8 5 3 7 7 7 8 2 4

Merk at dette kan brukes som en alternativ løsning på “Pyramid”-oppgaven, men sliding window er enklere.

OPPGAVE: “Beads” (oppgave F) fra IDI Open 2011 (testdata her). (Vi har ikke gitt noe pseudokode i denne artikkelen, for øket utfordring.)

Bonusoppgave (vi sier ikke hva løsningsmetoden er): “The valley of Mexico” fra IOI 2006 (datasett her).

Sliding window-algoritmer

La oss si at vi har en liste med n tall, og at vi ønsker å finne summen av alle sammenhengende dellister med k elementer (k <= n). Brute force-løsningen er:

for (int i = 0; i < n - k + 1; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += numbers[j];
    }
    cout << sum << endl;
}

Kjøretiden er O((n – k) * k), som tilsvarer O(n^2) hvis k er proporsjonal med n. Men trenger vi å regne ut hele summen på nytt for hvert element? Summen av element 1 til k er jo det samme som summen av element 0 til k – 1, bortsett fra at vi legger til element k og fjerner element 0. Dette kan vi fortsette med videre bortover – altså vedlikeholder vi en løpende sum over et “vindu” som vi skyver bortover, og hele tiden justere den ved å trekke fra elementet som forsvinner ut og legge til elementet som rykker inn. Dette kalles en sliding window-algoritme:

// Bygg opp det initielle vinduet
int windowSum = 0;
for (int i = 0; i < k; i++)
    windowSum += numbers[i];
cout << windowSum << endl;
// Skyv vinduet bortover (i markerer starten av det nye vinduet, 
// som altså starter på element i og slutter på element i + k - 1)
for (int i = 1; i < n - k + 1) {
    windowSum += numbers[i + k - 1] - numbers[i - 1];
    cout << windowSum << endl;
}

Men hva gjør vi når informasjonen om element x har rykket ut og element y har rykket inn ikke er nok til å svare på det vi lurer på om hvert vindu? Dette skjer eksempelvis når det vi lurer på er hva som er den største verdien i vinduet. Til dette kan vi bruke en heap, også kjent som en prioritetskø (priority queue). Denne datastrukturen kommer i to utgaver. En max-heap er en struktur hvor du kan legge inn elementer i en hvilken som helst rekkefølge, og hver gang du tar ut et element, vil du få det største elementet i heapen. En min-heap vil alltid gi deg det minste elementet. Å sette inn og å ta ut fra en heap som inneholder n elementer tar O(lg n) tid. Det anbefales å studere hvordan en heap er bygd opp, men til daglig bruker vi den ferdigbygde implementasjonen i C++, som heter priority_queue og ligger i <queue>.

Tanken er altså å bruke en heap til å holde rede på elementene som til enhver tid ligger i vinduet – dermed vet vi at det største elementet i vinduet vil ligge øverst i heapen. Men hvordan skal vi fjerne elementet som skal ut hver gang vi forskyver vinduet? Det å fjerne et element (annet enn toppelementet) fra en heap er egentlig ikke så vanskelig, men det krever at man vedlikeholder en peker til elementets plassering inni heapen, slik at man ikke bruker tid på å finne ut hvor elementet befinner seg. Dette støttes ikke av priority_queue i C++. Heldigvis kan man bruke følgende triks: vi kan ganske enkelt la være å fjerne elementene etterhvert som vi forskyver vinduet, men hver gang vi henter ut det største elementet, kontrollerer vi at elementet befinner seg inni det nåværende vinduet – hvis ikke, forkaster vi det og henter ut på nytt. For raskt å kunne finne ut hvorvidt elementet vi hentet ut av heapen befinner seg inni vinduet eller ikke, registrerer vi både tallverdien og indeksen når vi legger noe inn i heapen. Fordi heap-operasjonene har kjøretid O(lg n), blir det ingen merkbar ytelsesforskjell pga. de ekstra elementene. (Tilsvarende triks kan man bruke i Dijkstras korteste vei-algoritme.)

Når vi skal ha egendefinerte structs inni en heap, er vi nødt til å fortelle heapen hvordan elementene skal sorteres – dette må gjøres ved å overloade <-operatoren (og det må gjøres etter at man har definert structen, og før resten av koden). En detalj her er at priority_queue alltid er en max-heap, så hvis du ønsker en min-heap må du implementere den slik at hvis element a er mindre enn element b, slik at du vil at a skal havne øverst, må a < b returnere false (slik at heapen tror at a er størst og dermed skal gis ut først):

#include <queue>
#include <iostream>

using namespace std;

struct Entry {
    int value;
    int index;
};

bool operator < (const Entry & a, const Entry & b) {
    if (a.value == b.value)
        return a.index < b.index;
    return a.value < b.value;
}

OPPGAVE: Implementer resten av algoritmen for å finne største verdi inni et sliding window av størrelse k ved hjelp av en heap. Heapen kan deklareres slik: priority_queue<Entry> window;. Nye elementer deklareres og legges inn slik: Entry e = {someValue, someIndex}; window.push(e);. Største element hentes ut slik: Entry e = window.top();, og slettes slik: window.pop();. Løsningen står nedenfor.

int main() {
    // Les input
    int n, k;
    cin >> n >> k;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++)
        cin >> numbers[i];
    
    // Bygg opp det initielle vinduet
    priority_queue<Entry> window;
    for (int i = 0; i < k; i++) {
        Entry entry = {numbers[i], i};
        window.push(entry);
    }
    cout << window.top().value << endl;
    // top() returnerer toppelementet uten å fjerne det, 
    // og pop() fjerner toppelementet uten å returnere det, så man trenger begge to
    
    // Skyv vinduet bortover (i er elementet som skal inn, så i - k + 1 er det første elementet i det nye vinduet)
    for (int i = k; i < n; i++) {
        Entry newEntry = {numbers[i], i};
        window.push(newEntry);
        Entry greatest;
        while (true) {
            greatest = window.top();
            if (greatest.index > i - k) // Bare avbryt løkken dersom elementet vi fikk ut er inni det nåværende vinduet
                break;
            else
                window.pop();
        }
        cout << greatest.value << endl;
    }
}

Dersom man hadde slettet elementene fra heapen med en gang de gikk ut av vinduet, ville heapen aldri ha inneholdt mer enn k elementer, og kjøretiden ville ha blitt O(n lg k). Med vår fremgangsmåte risikerer vi at heapen ender opp med å inneholde alle elementene (hvilken situasjon vil forårsake dette?), så kjøretiden blir O(n lg n), som er omtrent like bra, og mye bedre enn O(n^2).

OPPGAVE: “Pyramid” fra IOI 2006 (testdata her). I tillegg til at det er to todimensjonale sliding windows inni hverandre (som man riktignok ikke trenger en heap til, så vidt jeg husker) trenger man et ekstra triks for å få optimal kjøretid.