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.
build(arr) {
const buildRecursive = (l, r) => {
if (l === r) return { sum: arr[l], left: null, right: null };
const mid = Math.floor((l + r) / 2);
const left = buildRecursive(l, mid);
const right = buildRecursive(mid + 1, r);
return { sum: left.sum + right.sum, left, right };
};
this.versions.push(buildRecursive(0, this.n - 1));
}
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.