Veel lõikude puudest

1. Tipus oma andmetüüpide hoidmine

Lõikude puud õpetatakse tavaliselt järgmise tüüpülesande kaudu.

Summa asemel võib olla ka mistahes muu operatsioon, näiteks tuleb leida hoopis \(\min(A[l], A[l + 1], \ldots, A[r])\), \(A[l] \cdot A[l + 1] \cdots A[r]\) vms. Tähistame puu operatsiooni \(\otimes\), s.t. vaja on leida

Ka ei pea massiivi elemendid olema konkreetselt täisarvud: sinna võib panna mistahes tüüpi elemente. Üks tingimus siiski on: operatsioon \(\otimes\) peab olema niisugune, et sulgude paigutusest midagi ei sõltu: iga \(a, b, c\) korral peab kehtima

C++ keeles võiks implementatsioon alata umbes niimoodi:

template<typename TSeg, TSeg (*op)(TSeg, TSeg), TSeg (*e)()>
class Segtree {
  // ...
};

Siin:

• TSeg on puus hoitav andmetüüp;
• op on tehe \(\otimes\);
• e on null muutuja funktsioon, mis tagastab tehte \(\otimes\) ühikelemendi.

Lõigu summa ülesannet peaks saama lahendada siis nii:

long long add (long long p, long long q) {
  return p + q;
}

long long e () {
  return 0;
}

// ...

int main () {
  // ...
  Segtree<long long, add, e> tree (n);

  // loe sisendist päringud ja kasuta meetodeid set ja query...
  // näiteks nii:
  tree.set(5, 10); // seame 5. positsioonil oleva arvu väärtuseks 10
  tree.query(3, 7); // leiab lõigu 3...7 summa
}

Lõigu miinimumi ülesanne lahenduks samamoodi, ainult add ja e tuleb ära vahetada.

Sellise "üldise" lõikude puu implemeteerimine on tugevalt soovituslik: paljusid järgmisi ülesandeid saab pärast seda ühe-kahe reaga lahendada.

1.1. Soojendus: noorim algkoosseis

Hoiame igas lõikude puu tipus sorteeritud listi vastava lõigu \(k\) vähimast elemendist. Selleks, et arvutada tipus olev list tema laste listide põhjal, paneme laste listid kokku, sorteerime ja jätame alles \(k\) esimest. Seda saab implemeteerida ka pisut efektiivsemalt, kasutades kahe pointeri meetodit.

Seega on puu igas tipus üks vector<int>. Tehe \(\otimes\) võtab argumentidena kaks vector<int> ja kombineerib need niimoodi kokku.

Siin ülesandes oli operatsioon \(\otimes\) sisuliselt ette antud. Raskemates ülesannetes see nii ei ole. Päris ülesannetes, kus lõikude puud vaja kasutada on, ei pruugi üldse mingeid päringuid olla: lihtsalt ülesande lahendamise käigus tuleb välja, et mingeid selliseid asju on vaja sageli üle arvutada. Enamasti on vaja tavalisi summasid ja miinimume arvutada, aga vahel on vaja ka midagi keerulisemat teha.

Ka sellest, kuidas seda "midagi keerulisemat" teha saab, tuleb ise aru saada: rasked ülesanded ei anna mingit imelikku operatsiooni ette. Seega harjutamiseks teeme näidetena läbi mõned veidramad sellised ülesanded.

1.2. Maksimaalne alamlõik

Alustame sellest, et liigume osasummade ehk prefiksisummade peale: arvutame massiivi \(B\), kus

ja \(B[0] = 0\). Siis on massiivi \(A\) lõigu \([l, r]\) summa lihtsalt \(B[r] - B[l - 1]\).

Niisiis saame ka päringu ümber kirjutada kujule:

• Antud \(l\) ja \(r\). Leia \(L, R\), kus \(l \le L < R \le r\) nii, et \(B[R] - B[L]\) on maksimaalne.

Selleks tuleb \(l\) pärast sisendist lugemist ühe võrra vähendada.

Kujutame ette, et meil on kaks massiivi \(B_1\) ja \(B_2\) ja me paneme nad otsapidi kokku massiiviks \(B_1 B_2\). Mis on massiivis \(B_1 B_2\) niisugune maksimaalse vahega paar?

On kolm võimalust:

• Maksimaalne paar asub täielikult \(B_1\) sees.
• Maksimaalne paar asub täielikult \(B_2\) sees.
• Maksimaalne paar koosneb \(B_1\) vähimast ja \(B_2\) suurimast elemendist.

Lõikude puu iga tipu kohta meelde jäetavast andmetüübist on hea mõelda kui lõigu "kokkuvõttest", mis sisaldab lõigu kohta kogu ülesande jaoks relevantset informatsiooni. Antud juhul on meil vaja kolme arvu: lõigu miinimum, lõigu maksimum ja lõigu sees olev maksimaalse vahega paar.

struct Seg {
  ll mn; // lõigu miinimum
  ll mx; // lõigu maksimum
  ll ans; // maksimaalse vahega paar
}

Operatsiooni \(\otimes\) mõtlesime me sisuliselt juba välja.

Seg op (Seg left, Seg right) {
  Seg ans;
  ans.mn = min(left.mn, right.mn);
  ans.mx = max(left.mx, right.mx);
  ans.ans = max(right.mx - left.mn, max(left.ans, right.ans));
  return ans;
}

Ja see ongi täislahendus. Arvutame prefiksisummade massiivi \(B\) ja ehitame lõikude puu, mille \(i\)-ndale elemendile vastavas lehes on strukt Seg { .mn = B[i], .mx = B[i], .ans = -INF };. Päringule vastamiseks leiame lõikude puus lõigu \([l, r]\) "summa".

1.3. Funktsioonide komponeerimine

Mõnikord on kasulik mõelda nii, et massiiv koosneb (väikese lähte- ja sihthulgaga) funktsioonidest ja päringule vastamiseks tuleb arvutada

ehk teisiti kirja panduna

mingi teatud \(x\) jaoks. Selgituseks teeme läbi ühe ülesande, kus niisugune mõtteviis kasulik on.

Alustame sellest, kuidas ülesannet ilma päringuteta lahendada. Tähistame \(i\)-ndal positsioonil olevat arvu kui \(A[i]\). Hakkame vasakult paremale välja arvutama, kas \(i\)-ndal positsioonil on miin; tähistame seda \(B[i]\). Paneme tähele, et kui teame \(B[i - 1]\) ja \(B[i]\), siis on meil vaja ainult vaadata \(A[i]\), et teada saada, mis on \(B[i + 1]\). Nimelt võtame \(A[i]\) ja lahutame sellest \(B[i - 1]\) ja \(B[i]\) seas olevate miinide arvu. Kui vastus on 0 või 1, siis vastavalt \(B[i + 1]\) on kas o või x. Muul juhul on sisendis vastuolu.

Näiteks kui \(B[i - 1] = \mathtt{o}\), \(B[i] = \mathtt{x}\) ja \(A[i] = 2\), siis \(B[i + 1] = \mathtt{x}\). Kui aga \(A[i] = 3\), siis on sisendis vastuolu.

1 / 15

❮

❯

\(A[i]\) on niisiis justkui funktsioon, mis teisendab paari \((B[i - 1], B[i])\) paariks \((B[i], B[i + 1])\). Täpsemalt vaatame funktsioone \(f_0, f_1, f_2, f_3\), mis vastavad juhtudele \(A[i] = 0, 1, 2, 3\). Funktsioonide toime paarile \((B[i - 1], B[i])\) võtab kokku allolev tabel.

Selleks, et arvutada \(B[i]\), tuleb meil niisiis välja arvutada

ja valida selle paari esimene element. Lisaks tuleb meil iga päringu juures kontrollida, et ülemine rida ei ole vastuoluline (vastuolu võib ilmneda alles pärast \(i\)-ndat positsiooni). Selleks arvutame

kus \(N\) on mingi piisavalt suur arv, et ükski päring sellest suuremaid arve enam mõjutanud pole.

Niisiis on meil massiiv, mis koosneb funktsioonidest \(S \to S\), kus \(S\) on viieelemendiline hulk \(\{ \mathtt{oo}, \mathtt{ox}, \mathtt{xo}, \mathtt{xx}, \mathtt{!} \}\). Peame aeg-ajalt arvutama välja massiivi mingi prefiksi kompositsiooni. Hoiame lõikude puu igas tipus vastavas lõigus olevate funktsioonide kompositsiooni. Kuna funktsioonid on viieelemendilisest hulgast viieelemendilisesse, siis esitame funktsiooni lihtsalt viieelemendilise massiivina. Operatsioon \(\otimes\) on tavaline funktsioonide komponeerimine.

enum State {
  OO = 0,
  OX = 1,
  XO = 2,
  XX = 3,
  CONTRA = 4
}

using Func = array<State, 5>;
Func op (Func left, Func right) {
  Func ans;
  for (int i = 0; i < 5; i++) {
    ans[i] = right[left[i]];
  }
  return ans;
}

1.4. Suluavaldise moodi komponeerimine

Suluavaldiseks nimetatakse sümbolitest ( ja ) moodustatud sõne. Ütleme, et suluavaldis on tasakaalus, kui sellest saab plusside ja ühtede vahele lisamisega moodustada matemaatiliselt korrektse avaldise. Näiteks (()) ja ()() on tasakaalus, aga (() ja ))(( ei ole.

Suluavaldiste kohta on läbi aegade formuleeritud palju huvitavaid ülesandeid. Lisaks on palju ülesandeid, mis küll ise suluavaldisi ei maini, aga mis taanduvad suluavaldiste peale või on suluavaldiselaadse struktuuriga. Osad neist lahenduvad ka lõikude puu abil. Mõned lihtsamad lahenduvad sümbolite ( ja ) asendamisega vastavalt arvudega \(+1\) ja \(-1\) ning võibolla näiteks prefiksisummade arvutamisega.

Raskemates võib aga kasulik olla järgmine teisendus. Defineerime funktsiooni \(\mathrm{reduce}(s)\), kus \(s\) on suluavaldis, järgmiselt: eemaldame avaldisest kõrvutiolevaid paare () nii kaua, kuni neid seal enam ei ole. Järele jääb sõne, kus on mingi arv \(a \ge 0\) sulge ) ja seejärel mingi arv \(b \ge 0\) sulge (, näiteks )))(((((. Ütleme, et \(\mathrm{reduce}(s)\) ongi see paar \((a, b)\).

Olgu \(s, t\) sõned. Tähistame \((a_1, b_1) = \mathrm{reduce}(s)\) ja \((a_2, b_2) = \mathrm{reduce}(t)\). Siis

Lisaks võime tähele panna, et \(s\) on tasakaalus parajasti siis, kui \(\mathrm{reduce}(s) = (0, 0)\). Mõnes ülesandes võib olla kasulik neid paare lõikude puu tippudes hoida, kasutades operatsiooni

Üks pisut raskem ülesanne, mida saab lahendada sarnase operatsiooniga on järgmine.

2. Laisad uuendused

Implementatsiooninäidetes kasutame igal pool järgmisi tähiseid. Eeldame, et massiivi enda pikkus on \(n\), mis on mingi kahe aste. Kui \(n\) ei ole kahe aste paneme massiivi otsa mõned (muidu kasutud) elemendid. Lõikude puu tipud on indeksitega \(1 \ldots 2n - 1\). Lehed ehk massiivile endale vastavad tipud on indeksitega \(n \ldots 2n - 1\); tipu \(u < n\) vasak laps on \(2u\) ja parem \(2u + 1\).

• tree[u] tähistab tipus \(u\) hoitavat väärtust;
• lfend[u] tähistab tipule \(u\) "kuuluva" lõigu vasakut otspunkti;
• rgend[u] tähistab tipule \(u\) "kuuluva" lõigu paremat otspunkti;
• lazy[u] tähistab tipus \(u\) olevat laiska märget.

2.1. Lõigu summa, lõigule liitmine

Idee on järgmine. Hoiame igas tipus "laiska märget": arvu \(x\). Selle märkme tähendus on: selles intervallis olevatele arvudele tuleb liita \(x\). Enne tipus oleva väärtuse (üks kõik milleks) kasutamist tuleb laisk märge tema lastele alla edasi lükata.

// u on tipu indeks
void propagate (int u) {
  // uuendame tipu väärtust
  // kui intervalli igale elemendile tuleb liita x,
  // siis intervalli summa kasvab x * (intervalli pikkus) võrra
  tree[u] += (rgend[u] - lfend[u] + 1) * lazy[u];

  // kui tipul on lapsi...
  if (u < n) {
    // lastes võib juba olla laisk märge
    // märkmed liituvad.
    lazy[2 * u] += lazy[u];
    lazy[2 * u + 1] += lazy[u];
  }

  lazy[u] = 0;
}

Teist tüüpi päringutele vastamine eriti ei muutu. Tuleb ainult meeles pidada, et enne tree[u] kasutamist tuleb laisk märge alla lükata, s.t. kutsuda propagate(u).

int sum (int l, int r, int u = 1) {
  // ainuke muutus on see:
  propagate(u);
  
  l = max(l, lfend[u]);
  r = min(r, rgend[u]);

  if (l > r)
    return 0;

  if (l == lfend[u] && r == rgend[u])
    return tree[u];

  return sum(l, r, 2 * u) + sum(l, r, 2 * u + 1);
}

Esimest tüüpi päringuid viime ellu enam-vähem nagu teist tüüpi päringuid — leiame võimalikult kõrgel olevad, päringu intervallis täielikult sisalduvad tipud ja paneme nendele laisad märked.

void update (int l, int r, int x, int u = 1) {
  propagate(u);

  l = max(l, lfend[u]);
  r = min(r, rgend[u]);

  if (l > r)
    return;

  if (l == lfend[u] && r == rgend[u]) {
    lazy[u] = x; // võib olla =, mitte +=, kuna tegime propagate
    propagate(u); // propagate, sest vanema juures kasutatakse tree[u]
    return;
  }

  update(l, r, x, 2 * u);
  update(l, r, x, 2 * u + 1);

  // päring uuendas summasid, korrekteerime tree[u]!
  tree[u] = tree[2 * u] + tree[2 * u + 1];
}

Keerukuse analüüs on sama, mis tavalise lõikude puu korral, ehk \(O(n + q \log n)\).

2.2. Lõigu summa, lõigule liitmine, lõigule seadmine

Teist tüüpi päringuid saame sõnastada ümber kujule: sea need kõik väärtused nulliks ja siis rakenda esimest tüüpi päringut. Laisa märkme võimalikud väärtused võtab kokku järgmine strukt:

struct Update {
  bool reset;
  int add;
};

Esimese tüübi korral kasutame kuju Update { .reset = false, .add = x }, teise tüübi korral Update { .reset = true, .add = x }. Tähelepanu tuleb pöörata propagate funktsioonile. Esimeses näites nägime, et tipu lastes võivad laisad märkmed juba olla. Sama kehtib ka siin. Peame kaks laiska märget "komponeerima" nii, et tulemusena tekkiv laisk märge toimiks puu tipul samamoodi nagu nende kahe märkme järjest rakendamine. Laiska uuendamist ei ole võimalik kasutada, kui laisku märkmeid ei ole võimalik mõistlikult komponeerida.

Antud juhul näeb komponeerimine välja midagi sellist:

/ first rakendatakse enne, second pärast
Update compose (Update first, Update second) {
  Update ans = first;
  if (second.reset) {
    ans.reset = true;
    ans.add = 0;
  }
  ans.add += second.add;

  return ans;
}

Kui teine uuendus väärtused nulliks seab, siis ei sõltu esimesest midagi. Kui ei sea, liidetavad väärtused liituvad. Meetod propagate(u) näeb nüüd välja nii:

void propagate(u) {
  // uuenduse toime muutub pisut keerulisemaks
  if (lazy[u].reset) {
    tree[u] = 0;
  }
  tree[u] += (rgend[u] - lfend[u] + 1) * lazy[u].add;

  if (u < n) {
    // lapses olev uuendus on enne lisatud ja rakendub esimesena
    lazy[2 * u] = compose(lazy[2 * u], lazy[u]);
    lazy[2 * u + 1] = compose(lazy[2 * u + 1], lazy[u]);
  }

  // nullimine - peab olema väärtus, mille rakendamine tipule
  // ei tee mitte midagi
  lazy[u] = Update {.reset = false, .add = 0};
}

2.3. Üldisem käsitlus

Nii nagu tavalise lõikude puu korral, on laiskade uuendustega lõikude puud võimalik kasutada suvaliste "oma" andmetüüpide jaoks. Paneme selguse mõttes kirja kõik andmetüübid ja funktsioonid, mida vaja on.

Tavalise lõikude puu jaoks on meil vaja:

• Seg, puu tipus hoitav andmetüüp;
• kahe muutuja funktsioon Seg op (Seg left, Seg right);
• konstant e tüüpi Seg,

kusjuures peavad kehtima järgmised võrdused kõikide võimalike a, b ja c korral:

• op(op(a, b), c) = op(a, op(b, c)),
• op(a, e) = a = op(e, a).

Laiskade uuenduste jaoks on lisaks vaja:

• Update, laisa märkme andmetüüp.
• Funktsioon Seg apply (Update update, Seg seg, int l, int r): uuenduse update rakendamine lõigule seg, mille otspunktid on vastavalt l ja r. Parameetrid l ja r võib ka ära jätta, kui näiteks lõigu pikkusest midagi ei sõltu.
• Funktsioon Update compose (Update first, Update second).
• Konstant id tüüpi Update, mis tähistab mitte millegi tegemist.

Peavad kehtima järgmised võrdused iga Seg a ja Update f, g, h korral:

• apply(f, apply(g, a)) = apply(compose(g, f), a),
• compose(h, compose(g, f)) = compose(compose(h, g), f),
• compose(f, id) = f = compose(id, f).

2.4. Ruutude summa

Vahel on vaja andmetüübis Seg hoida täiendavat informatsiooni, et laiskade märgete toimet välja arvutada. Üks selline ülesanne on järgmine.

Uurime, kuidas muutub lõigu ruutude summa pärast kõikidele elementidele \(x\) liitmist:

Uus ruutude summa sõltub ainult vanast ruutude summast, vanast summast ja lõigu elementide arvust.

Hoiame niisiis andmetüübis Seg kolme arvu: lõigu ruutude summa, lõigu summa ja lõigu elementide arv. (Viimast pole rangelt võttes vaja, kuna lõikude puu hoiab niikuinii meeles iga lõigu algus- ja lõpp-punkti).

struct Seg {
  int sumsq, sum, cnt;
};

Andmetüüp Update on lihtsalt täisarv, compose on liitmine ja id on null, nagu esimese lõigule liitmise ülesande korral. Selleks, et rakendada lõigule uuendust, arvutame kõigepealt ülaloleva valemi kaudu välja uue ruutude summa ja siis uue summa.

Seg apply (int x, Seg seg) {
  Seg ans;
  ans.sumsq = seg.sumsq + 2 * x * seg.sum + x * x * seg.cnt;
  ans.sum = seg.sum + x * seg.cnt;
  ans.cnt = seg.cnt;
  return ans;
};

Kahe lõigu kokkupanekul kõik summad liituvad:

Seg op (Seg left, Seg right) {
  return Seg {
    .sumsq = left.sumsq + right.sumsq,
    .sum = left.sum + right.sum,
    .cnt = left.cnt + right.cnt
  };
}

2.5. Teisi ülesandeid

Neid ülesandeid saab lahendada laiskade uuendustega nagu eelmiseidki. Formuleeri andmetüübid Seg ja Update, funktsioonid op, apply ja merge ning konstandid e ja id.