Persistent Segment Tree Basics

Persistence means old versions remain queryable after updates—you clone only O(log n) nodes per change on the update path.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Each version is a root pointer; unshared nodes are copied before mutation. Used for k-th in range, historical queries.

Try this in Python

# Persistent segtree: on update, clone nodes along the path (conceptual).
roots = []  # roots[v] = root after v-th update


def new_version_note() -> str:
    return "clone O(log n) nodes per update; keep old root intact"


print(new_version_note())

Common mistakes

• Mutating nodes shared by old versions.
• O(n) full copy per update.

Key takeaways

• New root = update(old_root, …) returning new root.
• Leaves still O(n) total space across versions with path copying.