Másolva!

Szegmensfa építés (Build)

A célunk egy olyan bináris fa létrehozása, amelynek levelei a tömb elemeit tárolják, a belső csomópontok pedig bizonyos intervallumok eredményeit (pl. összegeket) tartalmazzák.

A fa felépítése

  • A levelek az eredeti tömb elemei.
  • A belső csomópontok az alárendelt csomópontok értékeiből számított összeggel rendelkeznek.

Példa a fa felépítésére az összegzés műveletével:

            [36]
            /    \
        [9]      [27]
        /   \     /    \
    [4]   [5]  [16]   [11]
   /   \       /   \    
 [1]   [3]   [7]   [9]

A fa építésének lépései

  1. Az eredeti tömb elemeiből létrehozzuk a leveleket.
  2. Az egyes belső csomópontokat úgy számoljuk ki, hogy az alattuk lévő két gyermek csomópont értékeinek összegét vesszük.
  3. A folyamatot addig ismételjük, amíg el nem érjük a gyökércsomópontot, amely az egész tömb összegét tartalmazza.

Példakód egy szegmensfa építésére (összegzéssel)


        build(start, end, parent) {
            if (start === end) {
                return new Node(parent, this.numbers[start], [start, end], null);
            }

            let mid = Math.floor((start + end) / 2);

            let leftChild = this.build(start, mid, null);
            let rightChild = this.build(mid + 1, end, null);

            let value = leftChild.value + rightChild.value;

            let node = new Node(parent, value, [start, end], [leftChild, rightChild]);

            leftChild.parent = node;
            rightChild.parent = node;

            return node;
        }

Vesszővel elválasztva add meg az értékeket! Pl.: 9,15,12,68,91



Szegmensfa lekérdezése (Query)

A szegmensfa egyik legnagyobb előnye, hogy gyorsan tudunk intervallum lekérdezéseket végrehajtani. Például egy adott tartomány összegét kérdezhetjük le.

Intervallum lekérdezés működése

  • Megvizsgáljuk, hogy az aktuális csomópont teljesen, részben vagy egyáltalán nem esik-e a keresett intervallumba.
  • Ha teljesen kívül esik, nem vesszük figyelembe.
  • Ha teljesen belül van, közvetlenül felhasználjuk az értékét.
  • Ha részben átfedésben van, akkor tovább bontjuk a lekérdezést a gyermekeire.

Példa kód a lekérdezésre


        query(node, L, R) {
            if (!node || node.interval[1] < L || node.interval[0] > R) {
                return 0;
            }
            
            if (L <= node.interval[0] && node.interval[1] <= R) {
                return node.value;
            }
            
            let leftSum = this.query(node.children[0], L, R);
            let rightSum = this.query(node.children[1], L, R);
            
            return leftSum + rightSum;
        }

Ezzel a módszerrel gyorsan, O(log N) idő alatt végezhetünk intervallum lekérdezéseket.

Szegmensfa lekérdezés

Vesszővel elválasztva add meg az értékeket! Pl.: 9,15,12,68,91





Lekérdezés eredménye:
Lépések száma: 0

Szegmensfa Frissítés (Update)

A szegmensfa segítségével gyorsan frissíthetünk egy adott indexű elemet, és az érintett csomópontok újra kiszámításra kerülnek.

A frissítés működése

  • Keresd meg azt a levelet, amelyik az adott indexet tartalmazza.
  • Frissítsd az értékét az új értékre.
  • Haladj visszafelé a fában, és frissítsd az összes érintett csomópontot.

Példa kód a beszúrásra


            update(index, newValue) {
                // Kezdőpont a gyökér csomópont
                let node = this.root;
        
                // Rekurzívan keressük meg a levelet, amely tartalmazza az indexet
                while (node.interval[0] !== node.interval[1]) {
                    let mid = Math.floor((node.interval[0] + node.interval[1]) / 2);
        
                    if (index <= mid) {
                        node = node.children[0];
                    } else {
                        node = node.children[1];
                    }
                }
        
                // Frissítjük a levelet az új értékre
                let difference = newValue - node.value;
                node.value = newValue;
        
                // Visszafelé haladva frissítjük az ősök értékeit is
                let parent = node.parent;
                while (parent !== null) {
                    parent.value += difference;
                    parent = parent.parent;
                }
            }

Az update művelet is O(log N) időben fut, mivel csak egy útvonalon kell frissíteni az értékeket.

Szegmensfa Frissítése

Vesszővel elválasztva add meg az értékeket! Pl.: 9,15,12,68,91