A perzisztens szegmensfa egy speciális adatszerkezet, amely lehetővé teszi, hogy a múltbeli állapotokat is elérjük frissítések után. Ez különösen hasznos verziókezelésre vagy időbeli visszatekintésre algoritmusokban.
[36]
/ \
[9] [27]
/ \ / \
[4] [5] [16] [11]
/ \ / \
[1] [3] [7] [9]
A perzisztens szegmensfa rekurzív módon épül fel, ahol minden egyes verzió egy új fa, de az előző verzió csomópontjait újrahasználja, így hatékonyan kezeli a memóriát.
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
Amikor egy értéket frissítünk, egy új fa verzió jön létre, amely a régi csomópontokat újrahasználja.
function update(node, start, end, index, newValue) {
if (start === end) return new Node(newValue);
let mid = Math.floor((start + end) / 2);
if (index <= mid)
return new Node(node.value, update(node.left, start, mid, index, newValue), node.right);
else
return new Node(node.value, node.left, update(node.right, mid + 1, end, index, newValue));
}
A lekérdezés minden verzióból elérhető, így bármely múltbeli állapot visszahozható.
function query(node, start, end, l, r) {
if (start > r || end < l) return 0;
if (start >= l && end <= r) return node.value;
let mid = Math.floor((start + end) / 2);
return query(node.left, start, mid, l, r) + query(node.right, mid + 1, end, l, r);
}
Ez az oldal bemutatja a perzisztens szegmensfa működését interaktív verziókezeléssel.