Versioned Segment Tree

Versioned structures expose version or time parameter on queries—under the hood, persistent roots or rollback stacks.

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)

Rollback segtree: undo stack of changes for single-thread “time travel” without full persistence.

Try this in Python

versions: list[list[int]] = []


def snapshot(arr: list[int]) -> int:
    versions.append(arr.copy())
    return len(versions) - 1


a = [1, 2, 3]
snapshot(a)
a[0] = 99
print(versions[0], a)

Common mistakes

• Confusing rollback with persistence API.
• Querying wrong version after batch updates.

Key takeaways

• API: create_version(), query(v, l, r).
• Fenwick with rollback is simpler for sum-only.