Persistent yapılar ve augmentation

Persistent yapı güncelleme sonrası eski sürüme erişimi korur. Path copying değişen kök-yaprak yolunu kopyalar, değişmeyen alt ağaçları paylaşır. Bu deep copy değildir; immutable düğümler sayesinde paylaşım güvenlidir. Partial persistence eski sürümleri yalnız okumayı, full persistence eski sürümden yeni dal oluşturmayı destekler.

Persistent segment tree her point update'te O(log n) yeni düğüm üretir. Kökler listesi snapshot temsilidir. İki sürüm arasındaki farkla tarihsel prefix/range sorguları kurulabilir. Memory reclamation için sürüm yaşam süresini takip et; “immutable” olması sınırsız bellek kullanımı sorununu çözmez.

Augmentation'da subtree size, sum, maximum endpoint gibi yerel metadata tutulur. Interval tree overlap aramasında max endpoint ile dalları budar. Recompute yalnız çocuklardan O(1) hesaplanabiliyorsa rotasyon sonrası güncelleme ucuzdur. Paylaşılan eski düğümü mutate etmek bütün geçmişi bozabilir; API'de mutable/immutable ayrımı açık olmalıdır.

# Minimal immutable node; unchanged children may be shared.
from dataclasses import dataclass
@dataclass(frozen=True)
class Tree:
    total: int
    left: object = None
    right: object = None
old = Tree(3, Tree(1), Tree(2))
new = Tree(7, Tree(5), old.right)
assert old.total == 3 and new.right is old.right