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(startIndex, endIndex, parent = null) {
    const originalLength = endIndex - startIndex + 1;

    let size = 1;
    while (size < originalLength) size *= 2;

    let padded = this.numbers.slice(startIndex, endIndex + 1);
    while (padded.length < size) padded.push(0);

    const buildRecursive = (l, r, parent) => {
        const isLeafPadding = l >= originalLength;

        if (l === r) {
            return new Node(parent, padded[l], [l, l], null, isLeafPadding);
        }

        let mid = Math.floor((l + r) / 2);

        let leftChild = buildRecursive(l, mid, null);
        let rightChild = buildRecursive(mid + 1, r, null);

        let value = leftChild.value + rightChild.value;
        let isPadding = leftChild.isPadding && rightChild.isPadding;

        let node = new Node(parent, value, [l, r], [leftChild, rightChild], isPadding);

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

        return node;
    };

    return buildRecursive(0, size - 1, parent);
}

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 frissítésre


update(index, newValue) {
    let node = this.root;

    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];
        }
    }

    let difference = newValue - node.value;
    node.value = newValue;

    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





Szegmensfa Beszúrás (Insert)

A szegmensfa lehetővé teszi új elemek beszúrását és a megfelelő csomópontok frissítését.

A beszúrás működése

  • Ha van még padding levél:
    • Az első elérhető padding levélbe beírjuk az új értéket.
    • Frissítjük a szülőcsomópontokat visszafelé, és eltávolítjuk a padding jelzést, ha szükséges.
  • Ha nincs padding levél:
    • Létrehozunk egy új levelet az értékkel, és egy felfelé bővülő ágat építünk hozzá.
    • Végül új gyökércsomópontot hozunk létre, amely balra a régi fát, jobbra az új ágat tartalmazza.

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


insert(value) {
    const findFirstPaddingLeaf = (node) => {
        if (!node.children) {
            return node.isPadding ? node : null;
        }
        return findFirstPaddingLeaf(node.children[0]) || findFirstPaddingLeaf(node.children[1]);
    };

    let targetLeaf;
    if (this.root.children) {
        targetLeaf = findFirstPaddingLeaf(this.root.children[1]);
    } else {
        targetLeaf = findFirstPaddingLeaf(this.root);
    }

    if (targetLeaf) {
        const difference = value - targetLeaf.value;
        targetLeaf.value = value;
        targetLeaf.isPadding = false;
        this.numbers[targetLeaf.interval[0]] = value;

        let parent = targetLeaf.parent;
        while (parent !== null) {
            parent.value += difference;

            const [leafStart, leafEnd] = targetLeaf.interval;
            const [parentStart, parentEnd] = parent.interval;

            if (parent.isPadding && leafStart >= parentStart && leafEnd <= parentEnd) {
                parent.isPadding = false;
            }

            parent = parent.parent;
        }

    } else {
        const oldRoot = this.root;
        const newIndex = this.numbers.length;
        this.numbers.push(value);

        let newLeaf = new Node(null, value, [newIndex, newIndex], null, false);
        let branch = newLeaf;

        const isPowerOfTwo = (n) => (n & (n - 1)) === 0;
        let depth = 1;
        while (!isPowerOfTwo(this.numbers.length)) {
            let parent = new Node(null, branch.value, [newIndex, newIndex], [branch, null], false);
            branch.parent = parent;
            branch = parent;
            depth++;
            this.numbers.length++;
        }

        const newRoot = new Node(
            null,
            oldRoot.value + branch.value,
            [0, newIndex],
            [oldRoot, branch],
            false
        );
        oldRoot.parent = newRoot;
        branch.parent = newRoot;
        this.root = newRoot;
    }
}

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