I. Szegmensfa definició

A szegmensfa egy hatékony adatszerkezet, amelyet főként tartományokra vonatkozó műveletek gyors elvégzésére használnak. Egy bináris fa struktúrát használ, amely lehetővé teszi a tartományokra vonatkozó műveletek (pl. összegzés, minimum, maximum, LNKO) hatékony végrehajtását.

Fontos: A vizualizációk során kizárólag az összegzés műveletével fogunk dolgozni.

Amikor egy tömbben ismétlődő intervallum-lekérdezéseket végzünk (pl. egy adott tartomány összegét számítjuk), a naiv megoldás O(n) időben fut, ami nagyobb adathalmazoknál lassú lehet. Egy szegmensfa használatával viszont a lekérdezések és módosítások O(log n) idő alatt végrehajthatók, így sokkal hatékonyabb megoldást biztosít.

         [36]
        /    \
     [7]      [29]
    /  \      /   \    
 [4]  [3] [18]   [11]  

Jól látható, hogy az ábrán a levelek képviselik a tartomány egyes elemeit, továbbá mindegyik szülő node a két alatta lévő gyermek node összegéből adódik. Ebből következik, hogy a tömb amiből a fa épült: [4, 3, 18, 11]

II. Szegmensfa felépítése

Tegyük fel, hogy van egy tömbünk: [1, 3, 5, 7, 9, 11]. És tekintsük a következő kódot:

build(nodeIndex, left, right) {
  if (left === right) {
      this.tree[nodeIndex] = this.inputArray[left];
  } else {
      let mid = Math.floor((left + right) / 2);
      this.build(nodeIndex * 2, left, mid);
      this.build(nodeIndex * 2 + 1, mid + 1, right);
      this.tree[nodeIndex] = this.tree[nodeIndex * 2] + this.tree[nodeIndex * 2 + 1];
  }
}

Megjegyzés: A kód a statikus szegmensfa építési algoritmusát szemlélteti.

II. 3. Összegzés

A szegmensfa egy rendkívül hatékony és hasznos adatszerkezet, amely lehetővé teszi a gyors intervallum-lekérdezéseket. Kiemelkedő előnye az O(log n) időbonyolultságú műveletek, amelyek révén nagy adathalmazokkal is hatékonyan dolgozhatunk.

A szegmensfák tehát nem csupán egyszerű adatstruktúrák, hanem kulcsfontosságú szerepet játszanak a modern számítástechnika egyes területein, különösen a versenyprogramozásban és algoritmus-tervezésben. Alkalmazásuk számos különféle területen elterjedt, és lehetővé teszik a rendkívül hatékony adatkezelést és számításokat, még akkor is, ha az adatok dinamikusan változnak.

III. Különböző műveletek bemutatása

III. 1. Maximum művelet

A szegmensfa minden csúcsába a tartomány maximuma kerül. A lekérdezéshez a Math.max() használatos.

              [0,7] (30)
              /           \
        [0,3] (18)     [4,7] (30)
        /     \         /     \
      [0,1] [2,3]     [4,5] [6,7]
      (18)   (9)      (21)   (30)
    /   \   /   \    /   \   /   \
  (18)   (6)(9) (3) (15) (21) (12) (30)
          

Megjegyzés: Hatékony maximum keresés bármely intervallumban.

III. 2. LNKO művelet (Legnagyobb közös osztó)

Itt minden csomópont a szakasz LNKO-ját tárolja. A lekérdezésekhez az LNKO(a, b) műveletet alkalmazzuk.

                [0,7] (3)
                /          \
          [0,3] (3)      [4,7] (3)
          /     \         /     \
        [0,1] [2,3]     [4,5] [6,7]
        (6)    (3)      (3)    (6)
      /   \   /   \    /   \   /   \
  (18)   (6)(9)  (3)(15) (21) (12) (30)
          

Megjegyzés: Gyors és hatékony LNKO lekérdezések intervallumokra.

III. 3. Minimum művelet

A minimum szegmensfa minden szakasz legkisebb értékét tárolja, Math.min() alapján.

              [0,7] (3)
              /           \
        [0,3] (3)      [4,7] (12)
        /     \         /     \
      [0,1] [2,3]     [4,5] [6,7]
      (6)    (3)      (15)   (12)
    /   \   /   \    /   \   /   \
  (18)   (6)(9) (3) (15) (21) (12) (30)
      

Megjegyzés: Hasznos minimumok gyors kiszámításához bármely tartományban.

IV. Típusok összehasonlítása (statikus, dinamikus, perzisztens)

VI. Elméleti háttér

Tétel: A szegmensfa felépítése \( O(n) \) idő alatt elvégezhető.

Bizonyítás: A szegmensfa egy teljes bináris fa, amelynek csomópontjait egy \( 2n \) méretű tömbben tárolhatjuk.

1. Levelek inicializálása

Az eredeti tömb elemeit a levelekhez másoljuk:

\[ v[n+i] = a[i], \quad 0 \leq i < n \]

Ez \( O(n) \) időt igényel.

2. Belső csomópontok feltöltése

Alulról építjük a fát, minden belső csomópont értékét a gyerekeiből számítjuk ki:

\[ v[i] = f(v[2i], v[2i+1]) \]

Minden csomópontot pontosan egyszer számolunk ki, így az időbeli komplexitás:

\[ B(n) = B(n/2) + O(n) \Rightarrow O(n) \]

Következtetés

A szegmensfa felépítése \( O(n) \) idő alatt végrehajtható.

Tétel: A szegmensfa egy elemének módosítása \( O(\log n) \) idő alatt végrehajtható.

Bizonyítás: Egy módosítás során:

1. Levél megkeresése

A keresett indexű levélcsomópontot \( O(\log n) \) lépés alatt elérjük.

2. Érték frissítése

Az új értéket beállítjuk a levélben.

3. Felmenő csomópontok frissítése

A módosítás hatását végighúzzuk a szülőkön:

\[ v[i] = f(v[2i], v[2i+1]) \]

Mivel a fa magassága \( O(\log n) \), az időbeli komplexitás:

\[ U(n) = U(n/2) + O(1) \Rightarrow O(\log n) \]

Következtetés

A módosítás \( O(\log n) \) idő alatt végrehajtható.

Tétel: A szegmensfa lekérdezése \( O(\log n) \) idő alatt végrehajtható.

Bizonyítás: Egy adott \([L, R]\) intervallumra vonatkozó lekérdezés során:

1. Levelek elérése

Az indexeket a megfelelő levelekhez mozgatjuk.

2. Intervallum felbontása

A teljes intervallum lefedéséhez csak azokat a csomópontokat választjuk, amelyek teljes átfedésben vannak:

\[ \text{Ha } L \text{ páratlan, hozzáadjuk } v[L] \text{-t és } L++ \] \[ \text{Ha } R \text{ páros, hozzáadjuk } v[R] \text{-t és } R-- \]

Ezután \( L \) és \( R \) szülőire lépünk:

\[ L = L/2, \quad R = R/2 \]

Következtetés

Mivel a fa magassága \( O(\log n) \), a művelet legfeljebb ennyi lépést végez, és minden lépés \( O(1) \).

Az időbeli komplexitás:

\[ Q(n) = Q(n/2) + O(1) \Rightarrow O(\log n) \]

Tehát egy lekérdezés \( O(\log n) \) idő alatt végrehajtható.