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).

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>